[LeetCode] 1191. K-Concatenation Maximum Sum

[grandyang]

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 109 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

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

这道题给了一个数组 arr 和一个正整数k，说是数组可以重复k次，让找出最大的子数组之和。提到求子数组之和，那么肯定首推卡达内算法 Kadane's Algorithm，在之前的题目 Maximum Subarray 和 Maximum Subarray Sum with One Deletion 中也有应用到。但是你以为就是直接将数组重复k次，在新的大数组中直接用 Kadane 算法么，那就 Naive 了，好歹这也是道 Medium 的题目，得尊重一下。看一下数组长度和k值的范围，overflow 和 TLE 在向你招手，那该怎么办呢？还是来分析一下题目中的例子吧，例子1中数组全是正数，则最大和的子数组就是其本身，那么重复几次，就要都加上，就是原数组所有数字之和再乘以k。例子2中由于有负数存在，所以最大和只是某个子数组，这里就是单独的一个1，但是一旦可以重复了，那么首尾的1就可以连在一起，形成一个和为2的子数组了，但也不是连的越多越好，只有有首尾相连才可能使得正数相连，所以最多连2个就行了，因为这里整个数组之和为0，连再多跟没连一样。但如果把数组变为 [1,-2,2] 的话，那就不一样了，虽然说两个为 [1,-2,2,1,-2,2] 的最大子数组之和为3，但是由于原数组之和为1，只要尽可能多的连，就可以得到更大的值，所以这种情况也要考虑到。例子3中数组全是负数，则不管重复多少次，还是取空数组和为0。不得不说本题的例子给的不错，基本覆盖了大部分的情况，而且通过分析也大概可以得出解题思路了，就是根据k的大小，若等于1，则对原数组用 Kadane 算法，若大于1，则只拼接一个数组，那么这里就可以用 min(k, 2) 来合并这两种情况，不过在取数的时候，要用 arr[i % n] 来避免越界，这样就可以得到最大子数组之和了，不过这也还是针对 k 小于等于2的情况，对于 k 大于2的情况，还是要把减去2剩余的次数乘以整个数组之和的值加上，再一起比较，这样最终的结果就是三者之中的最大值了，参见代码如下：

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int res = INT_MIN, curSum = 0, n = arr.size(), M = 1e9 + 7;
        long total = accumulate(arr.begin(), arr.end(), 0);
        for (int i = 0; i < n * min(k, 2); ++i) {
            curSum = max(curSum + arr[i % n], arr[i % n]);
            res = max(res, curSum);
        }
        return max<long>({0, res, total * max(0, k - 2) + res}) % M;
    }
};

Github 同步地址:

#1191

类似题目：

Maximum Subarray

Maximum Subarray Sum with One Deletion

参考资料：

https://leetcode.com/problems/k-concatenation-maximum-sum/

https://leetcode.com/problems/k-concatenation-maximum-sum/discuss/382885/Short-and-concise-O(N)-C%2B%2B-solution

https://leetcode.com/problems/k-concatenation-maximum-sum/discuss/382350/Java-Solution(Kadens-Algo)-with-Explanation

LeetCode All in One 题目讲解汇总(持续更新中...)