LEETCODE 1191. K-Concatenation Maximum Sum 解题思路分析

题目大意:

K 次串联后最大子数组之和

给你一个整数数组 arr 和一个整数 k

首先,我们要对该数组进行修改,即把原数组 arr 重复 k 次。

举个例子,如果 arr = [1, 2] 且 k = 3,那么修改后的数组就是 [1, 2, 1, 2, 1, 2]

然后,请你返回修改后的数组中的最大的子数组之和。

注意,子数组长度可以是 0,在这种情况下它的总和也是 0

由于 结果可能会很大,所以需要 模(mod)10^9 + 7 后再返回。

示例 1:

输入:arr = [1,2], k = 3
输出:9

示例 2:

输入:arr = [1,-2,1], k = 5
输出:2

示例 3:

输入:arr = [-1,-2], k = 7
输出:0

提示:

  • 1 <= arr.length <= 10^5
  • 1 <= k <= 10^5
  • -10^4 <= arr[i] <= 10^4

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1191

解题思路分析:

这是一道求连续区间和最大的问题。最开始打算暴力解,不过看了一下数量级,数组长度为10万,重复次数为10万,这样组合成的最大数组长度会达到100亿,即使时间复杂度为O(n)也会超时。因此我们应该分析一下更优的解法。

先考虑这个最大连续区间和会出现在什么地方?

  1. 单独数组的中间部分
  2. 数组头 + 数组尾
  3. 数组尾 + (k – 2) * 数组和 + 数组头

分别举例来说明一下:

arr = [-100, 5, -100] // 单独数组的中间部分为最大值
// [-100, 5, -100, -100, 5, -100, -100, 5, -100, ......]
// 即使将数组重复N次,连续区间最大和都是5。
arr = [1, -100, 5] // 数组头 + 数组尾为最大值
// [1, -100, 5, 1, -100, 5, 1, -100, 5, ......]
// 连续区间最大和为5+1=6。
arr = [-2, 1, 5] // 数组尾 + (k - 2) * 数组和 + 数组头为最大值
// [-2, 1, 5, -2, 1, 5, -2, 1, 5, ......, -2, 1, 5]
// 此时数组尾是 1 + 5 = 6,数组头是 -2 + 1 + 5 = 4
// 中间部分是(k - 2) * 数组和

因此我们可以分别求出上述三种情况的的最大值,在其中再选出最大的一个即是答案。注意,数组头部连续最大和的长度可能会是0到数组长度区间,中间和尾部也同样。

看下完整的实现代码:

public int kConcatenationMaxSum(int[] arr, int k) {
    long presum=0; // 前缀和
    long maxpresum=0; // 最大前缀和
    long endsum=0; // 后缀和
    long maxendsum=0; // 最大后缀和
    long subsum=0; // 中间子数组和
    long maxsubsum=0; // 最大中间子数组和
    for(int i=0;i<arr.length;i++){ // 循环数组
        presum += arr[i]; // 累加前缀和
        maxpresum = Math.max(presum, maxpresum); // 更新最大前缀和
        endsum += arr[arr.length-1-i]; // 累加后缀和
        maxendsum = Math.max(endsum, maxendsum); // 更新最大后缀和
        // 计算中间和
        if(subsum < 0){ // 如果中间和小于0,它加上当前数一定小于当前数
            subsum=arr[i]; // 中间和舍弃之前数字,更新为当前数字
        }else{
            subsum+=arr[i]; // 中间和加上当前数字
        }
        maxsubsum = Math.max(subsum, maxsubsum); // 更新最大中间和
    }
    if(k==1){ // 如果数组只重复1次
        return (int)(maxsubsum % 1000000007); // 直接返回最大中间和
    }else{
        // 计算出三种情况,取最大值为返回结果
        int max1 = (int)(maxsubsum % 1000000007);
        int max2 = (int)((maxpresum + maxendsum) % 1000000007);
        int max3 = (int)((maxpresum + maxendsum + presum *(k-2)) % 1000000007);
        return Math.max(Math.max(max1, max2), max3);
    }
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 74.45% of Java online submissions for K-Concatenation Maximum Sum.

Memory Usage: 49.9 MB, less than 100.00% of Java online submissions for K-Concatenation Maximum Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1191-k-concatenation-maximum-sum-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 1191. K-Concatenation Maximum Sum 解题思路分析》有2条回应

    发表评论

    您的电子邮箱地址不会被公开。