1191. K-Concatenation Maximum Sum

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 SubarrayMaximum 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation