Medium
题目描述
给定一个整数数组 arr 和一个整数 k，通过重复数组 k 次来修改数组。
例如，如果 arr = [1, 2] 且 k = 3，那么修改后的数组将是 [1, 2, 1, 2, 1, 2]。
返回修改后数组中的最大子数组和。注意子数组的长度可以是 0，在这种情况下它的和为 0。
由于答案可能很大，请返回答案对 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^51 <= k <= 10^5-10^4 <= arr[i] <= 10^4
解题思路
这道题需要分情况讨论来解决：
核心思路：
- k=1 的情况：直接使用 Kadane 算法求最大子数组和
- k>1 的情况：需要考虑三种可能的最大子数组位置：
- 完全在某一个数组副本内（与k=1相同）
- 跨越数组边界，包含前缀和后缀
- 包含完整的中间数组副本
具体分析：
- 先计算原数组的总和
totalSum、最大前缀和maxPrefix、最大后缀和maxSuffix - 使用 Kadane 算法计算单个数组的最大子数组和
maxKadane - 对于 k=1，答案就是
max(0, maxKadane) - 对于 k>1：
- 如果
totalSum > 0，最优解可能是maxSuffix + maxPrefix + (k-2) * totalSum - 否则最优解是跨越两个数组的子数组，即在两个连续副本中用 Kadane 算法
- 如果
- 取所有情况的最大值
时间优化：
当 k>1 时，我们只需要考虑两个连续的数组副本，因为如果包含更多完整副本且 totalSum ≤ 0，答案不会更优。
代码实现
class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
const int MOD = 1e9 + 7;
int n = arr.size();
// Calculate total sum
long long totalSum = 0;
for (int x : arr) {
totalSum += x;
}
// Kadane's algorithm for single array
long long maxKadane = 0, currentSum = 0;
for (int x : arr) {
currentSum = max((long long)x, currentSum + x);
maxKadane = max(maxKadane, currentSum);
}
if (k == 1) {
return maxKadane % MOD;
}
// Calculate max prefix sum
long long maxPrefix = 0, prefixSum = 0;
for (int x : arr) {
prefixSum += x;
maxPrefix = max(maxPrefix, prefixSum);
}
// Calculate max suffix sum
long long maxSuffix = 0, suffixSum = 0;
for (int i = n - 1; i >= 0; i--) {
suffixSum += arr[i];
maxSuffix = max(maxSuffix, suffixSum);
}
// Kadane on two concatenated arrays
long long maxTwo = 0;
currentSum = 0;
for (int i = 0; i < 2 * n; i++) {
currentSum = max((long long)arr[i % n], currentSum + arr[i % n]);
maxTwo = max(maxTwo, currentSum);
}
long long result = maxTwo;
if (totalSum > 0) {
result = max(result, maxSuffix + maxPrefix + (k - 2) * totalSum);
}
return result % MOD;
}
};
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
MOD = 10**9 + 7
n = len(arr)
# Calculate total sum
total_sum = sum(arr)
# Kadane's algorithm for single array
max_kadane = current_sum = 0
for x in arr:
current_sum = max(x, current_sum + x)
max_kadane = max(max_kadane, current_sum)
if k == 1:
return max_kadane % MOD
# Calculate max prefix sum
max_prefix = prefix_sum = 0
for x in arr:
prefix_sum += x
max_prefix = max(max_prefix, prefix_sum)
# Calculate max suffix sum
max_suffix = suffix_sum = 0
for x in reversed(arr):
suffix_sum += x
max_suffix = max(max_suffix, suffix_sum)
# Kadane on two concatenated arrays
max_two = current_sum = 0
for i in range(2 * n):
current_sum = max(arr[i % n], current_sum + arr[i % n])
max_two = max(max_two, current_sum)
result = max_two
if total_sum > 0:
result = max(result, max_suffix + max_prefix + (k - 2) * total_sum)
return result % MOD
public class Solution {
public int KConcatenationMaxSum(int[] arr, int k) {
const int MOD = 1000000007;
int n = arr.Length;
// Calculate total sum
long totalSum = arr.Sum(x => (long)x);
// Kadane's algorithm for single array
long maxKadane = 0, currentSum = 0;
foreach (int x in arr) {
currentSum = Math.Max(x, currentSum + x);
maxKadane = Math.Max(maxKadane, currentSum);
}
if (k == 1) {
return (int)(maxKadane % MOD);
}
// Calculate max prefix sum
long maxPrefix = 0, prefixSum = 0;
foreach (int x in arr) {
prefixSum += x;
maxPrefix = Math.Max(maxPrefix, prefixSum);
}
// Calculate max suffix sum
long maxSuffix = 0, suffixSum = 0;
for (int i = n - 1; i >= 0; i--) {
suffixSum += arr[i];
maxSuffix = Math.Max(maxSuffix, suffixSum);
}
// Kadane on two concatenated arrays
long maxTwo = 0;
currentSum = 0;
for (int i = 0; i < 2 * n; i++) {
currentSum = Math.Max(arr[i % n], currentSum + arr[i % n]);
maxTwo = Math.Max(maxTwo, currentSum);
}
long result = maxTwo;
if (totalSum > 0) {
result = Math.Max(result, maxSuffix + maxPrefix + (k - 2) * totalSum);
}
return (int)(result % MOD);
}
}
var kConcatenationMaxSum = function(arr, k) {
const MOD = 1000000007;
const n = arr.length;
function kadane(nums) {
let maxSum = 0;
let currentSum = 0;
for (let num of nums) {
currentSum = Math.max(0, currentSum + num);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
if (k === 1) {
return kadane(arr) % MOD;
}
const totalSum = arr.reduce((sum, num) => sum + num, 0);
const doubleArr = [...arr, ...arr];
const maxInDouble = kadane(doubleArr);
if (totalSum <= 0) {
return maxInDouble % MOD;
}
const maxPrefix = kadane(arr.slice().reverse()).valueOf();
let prefixSum = 0;
let maxPrefixSum = 0;
for (let num of arr) {
prefixSum += num;
maxPrefixSum = Math.max(maxPrefixSum, prefixSum);
}
let suffixSum = 0;
let maxSuffixSum = 0;
for (let i = n - 1; i >= 0; i--) {
suffixSum += arr[i];
maxSuffixSum = Math.max(maxSuffixSum, suffixSum);
}
const result = Math.max(maxInDouble, (maxPrefixSum + maxSuffixSum + (k - 2) * totalSum) % MOD);
return result % MOD;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n)，其中 n 是数组长度。虽然有多次遍历，但都是常数次，总体仍为线性时间 |
| 空间复杂度 | O(1)，只使用了常数额外空间存储各种和值 |