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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1191-k-concatenation-maximum-sum-解题思路分析/