Question

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

English Version

题目描述

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

解法

方法一：前缀和 + 分类讨论

我们记数组 $arr$ 所有元素之和为 $s$，最大前缀和为 $mxPre$，最小前缀和为 $miPre$，最大子数组和为 $mxSub$。

遍历数组 $arr$，对于每个元素 $x$，我们更新 $s = s + x$, $mxPre = \max(mxPre, s)$, $miPre = \min(miPre, s)$, $mxSub = \max(mxSub, s - miPre)$。

接下来，我们考虑 $k$ 的取值情况：

• 当 $k = 1$ 时，答案为 $mxSub$。
• 当 $k \ge 2$ 时，如果最大子数组横跨两个 $arr$，那么答案为 $mxPre + mxSuf$，其中 $mxSuf = s - miPre$。
• 当 $k \ge 2$ 且 $s > 0$ 时，如果最大子数组横跨三个 $arr$，那么答案为 $(k - 2) \times s + mxPre + mxSuf$。

最后，我们返回答案对 $10^9 + 7$ 取模的结果。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $arr$ 的长度。

class Solution:
  def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
    s = mx_pre = mi_pre = mx_sub = 0
    for x in arr:
      s += x
      mx_pre = max(mx_pre, s)
      mi_pre = min(mi_pre, s)
      mx_sub = max(mx_sub, s - mi_pre)
    ans = mx_sub
    mod = 10**9 + 7
    if k == 1:
      return ans % mod
    mx_suf = s - mi_pre
    ans = max(ans, mx_pre + mx_suf)
    if s > 0:
      ans = max(ans, (k - 2) * s + mx_pre + mx_suf)
    return ans % mod

class Solution {
  public int kConcatenationMaxSum(int[] arr, int k) {
    long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
    for (int x : arr) {
      s += x;
      mxPre = Math.max(mxPre, s);
      miPre = Math.min(miPre, s);
      mxSub = Math.max(mxSub, s - miPre);
    }
    long ans = mxSub;
    final int mod = (int) 1e9 + 7;
    if (k == 1) {
      return (int) (ans % mod);
    }
    long mxSuf = s - miPre;
    ans = Math.max(ans, mxPre + mxSuf);
    if (s > 0) {
      ans = Math.max(ans, (k - 2) * s + mxPre + mxSuf);
    }
    return (int) (ans % mod);
  }
}

class Solution {
public:
  int kConcatenationMaxSum(vector<int>& arr, int k) {
    long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
    for (int x : arr) {
      s += x;
      mxPre = max(mxPre, s);
      miPre = min(miPre, s);
      mxSub = max(mxSub, s - miPre);
    }
    long ans = mxSub;
    const int mod = 1e9 + 7;
    if (k == 1) {
      return ans % mod;
    }
    long mxSuf = s - miPre;
    ans = max(ans, mxPre + mxSuf);
    if (s > 0) {
      ans = max(ans, mxPre + (k - 2) * s + mxSuf);
    }
    return ans % mod;
  }
};

func kConcatenationMaxSum(arr []int, k int) int {
  var s, mxPre, miPre, mxSub int
  for _, x := range arr {
    s += x
    mxPre = max(mxPre, s)
    miPre = min(miPre, s)
    mxSub = max(mxSub, s-miPre)
  }
  const mod = 1e9 + 7
  ans := mxSub
  if k == 1 {
    return ans % mod
  }
  mxSuf := s - miPre
  ans = max(ans, mxSuf+mxPre)
  if s > 0 {
    ans = max(ans, mxSuf+(k-2)*s+mxPre)
  }
  return ans % mod
}