原文链接: https://leetcode-cn.com/problems/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 <= 105
• 1 <= k <= 105
• -104 <= arr[i] <= 104

中文题目

给你一个整数数组 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

通过代码

高赞题解

预备知识

首先，关于“最大子数组和”问题有一个基于动态规划的经典算法Kadane算法。这个算法使用maxOfEnd表示以当前数组元素结尾的最大和子数组，转移过程也十分简单——要么就是只取当前元素，要么就是拖家带口把前一元素的maxOfEnd一起带上。上图的例子，我们使用以下的Kadane算法，可以得到最大子数组和为55 + 66 = 121。

int largestSubarraySum(int[] arr) {
  int maxOfEnd, maxSoFar;
  maxSoFar = maxOfEnd = arr[0] > 0 ? arr[0] : 0;
  for (int i = 1; i < arr.length; i++) {
    maxOfEnd = Math.max(maxOfEnd + arr[i], arr[i]);
    maxSoFar = Math.max(maxOfEnd, maxSoFar);
  }
  return maxSoFar;
}

算法

回到问题本身，由于数组可以重复出现，所以实际上，我们的子数组是可以跨过原始数组arr的边界的。如果我们限制子数组长度在arr.length以内，那么问题将转变为“最大子数组和”的变种，即子数组可以是以下两种形式：

• 形式 1: 常规型，就是通常意义的子数组。formal(i, j)定义为:
  arr[i] + arr[i+1] + ... + arr[j], 其中0 <= i <= j < arr.length
• 形式 2: 非常规型，这种子数组分为两段，第一段从原始数组的首元素开始，第二段以原始数组的末元素结尾。很显然，非常规型数组的数量与常规型的一样多。nonformal(i, j)定义为：
  arr[0] + arr[1] + ... + arr[i] + arr[j] + arr[j+1] + ... + arr[arr.lengh-1], 其中0 <= i <= j < arr.length

上面这个变种问题，我们可以通过下面的算法来解决：我们准备两个arr，然后对它执行Kadane算法，这样我们得到的结果一定涵盖了上面两种类型的子数组。

int largestSubarraySum(int[] arr) {
  int maxOfEnd, maxSoFar, len = arr.length;
  maxSoFar = maxOfEnd = arr[0] > 0 ? arr[0] : 0;
  for (int i = 1; i < len * 2; i++) {
    maxOfEnd = Math.max(maxOfEnd + arr[i % len], arr[i % len]);
    maxSoFar = Math.max(maxOfEnd, maxSoFar);
  }
  return maxSoFar;
}

然而，上面的算法实际上给出的结果是maxSoFar = 185(Pic iii, 红色部分)。这是什么呢？

我们把结果分成两部分，蓝色和绿色。可以看出，这是一个常规型的子数组（蓝色）加上一个完整的原始数组arr得到的。[55, 66]是所有常规和非常规子数组中最大的，但是因为sum(arr) > 0，所以它还可以被扩展一个arr.length的长度。因此，我们可以得出最后的算法，如果sum(arr) > 0，maxSoFar可以反复叠加k - 2次。k == 1的边界条件可以小心处理一下。

update 2021.01.28 官方测试用例新增了”[10000, 10000, 10000, …], 2”，会绕过while循环，导致最终结果未mod(1000000007)。已经在return语句增加了对这个corner case的处理。

class Solution {
  public int kConcatenationMaxSum(int[] arr, int k) {
    if (arr == null || arr.length == 0) return 0;
    long maxOfEnd = arr[0] > 0 ? arr[0] : 0L, maxSoFar = maxOfEnd, sum = arr[0];
    for (int i = 1; i < Math.min(k, 2) * arr.length; i++) {
      maxOfEnd = Math.max(maxOfEnd + arr[i % arr.length], arr[i % arr.length]);
      maxSoFar = Math.max(maxOfEnd, maxSoFar);
      if (i < arr.length) sum += arr[i];
    }
    while (sum > 0 && --k >= 2)
      maxSoFar = (maxSoFar + sum) % 1000000007;
    return (int) maxSoFar % 1000000007;
  }
}

复杂度

时间 O(N)，N为原始数组的长度； 空间 O(1)

进一步证明

定义：数组arr的所有元素之和为sum(arr)，arr重复k次表示为carr(k) (k >= 2)。那么carr(k)中所有的子数组可以写为：

• formal(i, j) + carr(n), where n = 0, 1, 2, ..., k - 1 and 0 <= i <= j <= len(arr) - 1
• nonformal(i, j) + carr(m), where m = 0, 1, 2, ..., k - 2 and 0 <= i <= j <= len(arr) - 1

显然，sum(arr) <= 0时，所有长度超过len(arr)的子数组不可能比formal(i, j)和nonformal(i, j)中的最大子数组大。而当sum(arr) > 0时：

• formal(i, j) + carr(n)之和可以写成sum(formal(i, j)) + sum(arr) + r * sum(arr)
• nonformal(i, j) + carr(m)之和可以写成sum(nonformal(i, j)) + r * sum(arr)

这里，0 <= r <= k - 2。所以问题的关键就在于求出sum(formal(i, j) + sum(arr)和sum(nonformal(i, j)的最大值，而这个问题恰恰用carr(2)的Kadane算法就可以求解。图(iv) 中给出了一些例子。

统计信息

通过次数	提交次数	AC比率
6159	23093	26.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言