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

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大 ，需要返回的 109 + 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 <= 105
1 <= k <= 105
-104 <= arr[i] <= 104

预备知识

首先，关于“最大子数组和” 问题有一个基于动态规划的经典算法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) 中给出了一些例子。