1191 K-Concatenation Maximum Sum K 次串联后最大子数组之和
Description:
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:
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 次来修改数组。
例如，如果 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 <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
思路:
模拟
当 k = 1 时, 转化为最大连续子数组和, 注意答案非负
当 k = 2 时, 为数组最大前缀和和最大后缀和的和
当 k > 2 时, 如果数组的和为正, 需要加上 sum * (k - 2)
时间复杂度为 O(n), 空间复杂度为 O(n)
代码:
C++:
class Solution
{
public:
int kConcatenationMaxSum(vector<int>& arr, int k)
{
int n = arr.size(), pre = 0, result = 0, mod = 1e9 + 7, sum = 0;
for (int i = 0; i < (n << 1); i++)
{
pre = max(arr[i % n], pre + arr[i % n]);
result = max(result, pre);
if (k == 1 and i == n - 1) return result;
if (i < n) sum += arr[i];
}
return (int)((max(0, sum) * (long)(k - 2) + result) % mod);
}
};
Java:
class Solution {
public int kConcatenationMaxSum(int[] arr, int k) {
int n = arr.length, pre = 0, result = 0, mod = 1_000_000_007, sum = 0;
for (int i = 0; i < (n << 1); i++) {
pre = Math.max(arr[i % n], pre + arr[i % n]);
result = Math.max(result, pre);
if (k == 1 && i == n - 1) return result;
if (i < n) sum += arr[i];
}
return (int)((Math.max(0, sum) * (long)(k - 2) + result) % mod);
}
}
Python:
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
result, pre, s, mod = 0, 0, sum(arr), 10 ** 9 + 7
arr *= min(k, 2)
for i, v in enumerate(arr):
result = max(result, (pre := max(v, v + pre)))
return (max(result, s * (k - 2) + result) if (s > 0 and k > 2) else result) % mod
