LeetCode 1191. K 次串联后最大子数组之和
题目描述
题意分析
将原数组按顺序连续拼接
k次，在得到的长数组中选择一个连续子数组，使总和最大，最后返回这个最大值对10^9 + 7取模的结果。允许选择长度为零的空子数组，其和为零，因此答案不会为负。重复次数可能很大，不需要也不应真的构造全部
k份内容；先确定真实最大和，再对最终结果取模。
解法：Kadane + 前后缀最大和
核心思路
[!blue]
先分类最大子数组的位置。如果它完全位于某一个副本内部，各副本内容相同，只需求原数组内的最大子数组和
bestOne。Kadane 用cur记录以当前扫描位置结束的最优非负贡献：接上当前数后若总和为负，就舍弃这段、重新从零开始；再用bestOne保存全局最大值。如果子数组跨越多个副本，连续性要求它一定由起始副本的一段后缀、中间若干完整副本和末尾副本的一段前缀组成，不能跳过某个副本中的内部元素。分别求原数组的最大后缀和
bestSuffix、最大前缀和bestPrefix，以及整份总和sum。当
k >= 2时，至少可以把后缀与前缀放在相邻两份中，形成候选bestSuffix + bestPrefix。若sum > 0，每多包含一个完整副本都会增加收益，就使用最多的k - 2个中间副本；若sum <= 0，加入中间整份不会更好，直接使用相邻两份已经足够。首尾片段来自不同副本，所以可以独立取各自最大值。
k = 1时没有这种独立性，不能把同一数组的两端直接拼在一起，必须只返回单份最优。最大前缀、后缀和单份最优都允许从零开始；空端点只会退化成合法的单份片段或空段，不会抬高为一个不存在的结果。将单份最优与跨副本候选取最大，已经覆盖所有可能形态。真实总和、候选乘积都用 64 位整数保存；取模不保持大小关系，所以在选择最大值之前不能对这些状态取模。
解题步骤
- 对原数组运行允许空段的 Kadane，得到
bestOne。- 正向累计求最大前缀和与总和，反向累计求最大后缀和。
- 初始化答案为单份最优；只有
k > 1才计算前后缀相加的跨副本候选。- 总和为正时，再为跨副本候选加入
(k - 2) * sum；否则不增加完整中间副本。- 比较两种候选的真实值，最后对最大结果取模并返回。
代码实现
class Solution {
private static final int MOD = 1_000_000_007;
public int kConcatenationMaxSum(int[] arr, int k) {
// 形态 A：完全落在一段内。初值 0 表示允许空子数组。
long bestOne = 0;
long cur = 0;
for (int v : arr) {
cur = Math.max(0, cur + v);
bestOne = Math.max(bestOne, cur);
}
long sum = 0;
// 空前缀允许贡献零，避免强行选入负收益。
long bestPrefix = 0;
long prefix = 0;
for (int v : arr) {
prefix += v;
bestPrefix = Math.max(bestPrefix, prefix);
sum += v;
}
long bestSuffix = 0;
long suffix = 0;
for (int i = arr.length - 1; i >= 0; i--) {
suffix += arr[i];
bestSuffix = Math.max(bestSuffix, suffix);
}
long answer = bestOne;
// 至少有两个副本，最大前后缀才来自可独立选择的位置。
if (k > 1) {
// 形态 B：后缀 + 前缀；sum > 0 时再补上 k-2 个完整段（形态 C）。
long cross = bestPrefix + bestSuffix;
if (sum > 0) {
cross += (long) (k - 2) * sum;
}
answer = Math.max(answer, cross);
}
// 只在最后取模，中间取模会破坏 max 的比较。
return (int) (answer % MOD);
}
}
func kConcatenationMaxSum(arr []int, k int) int {
const mod = 1000000007
// 形态 A：完全落在一段内。初值 0 表示允许空子数组。
bestOne := int64(0)
cur := int64(0)
for _, v := range arr {
cur = max64(0, cur+int64(v))
bestOne = max64(bestOne, cur)
}
sum := int64(0)
// 空前缀允许贡献零，避免强行选入负收益。
bestPrefix := int64(0)
prefix := int64(0)
for _, v := range arr {
prefix += int64(v)
if prefix > bestPrefix {
bestPrefix = prefix
}
sum += int64(v)
}
bestSuffix := int64(0)
suffix := int64(0)
for i := len(arr) - 1; i >= 0; i-- {
suffix += int64(arr[i])
if suffix > bestSuffix {
bestSuffix = suffix
}
}
answer := bestOne
// 至少有两个副本，最大前后缀才来自可独立选择的位置。
if k > 1 {
// 形态 B：后缀 + 前缀；sum > 0 时再补上 k-2 个完整段（形态 C）。
cross := bestPrefix + bestSuffix
if sum > 0 {
cross += int64(k-2) * sum
}
if cross > answer {
answer = cross
}
}
// 只在最后取模，中间取模会破坏比较。
return int(answer % mod)
}
func max64(a, b int64) int64 {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，对原数组只做常数次扫描，实际工作量不随
k扩大。- 空间复杂度：$O(1)$，使用固定数量的 64 位累计值，不复制任何副本。
关键点总结
[!green]
- 连续子数组要么留在单份内部，要么是后缀、完整中段、前缀三部分。
- 整份总和的正负决定中间副本取最多还是不取。
- 单份场景必须独立处理，首尾最优只有放在不同副本才可以自由组合。
- 空段与最后取模分别对应题目的两个边界要求，不能按普通非空 Kadane 直接照搬。
易错点总结
[!yellow]
- 总和为负时仍加入全部中间副本，会主动降低原本更好的跨相邻副本答案。
- 只有一个副本时仍拼接前后缀，可能把中间必须连续包含的负值跳过去。
- 中间数量写成
k - 1，没有扣除已经承担首尾片段的两个副本。- 最大和初始化为负数或强制非空，会在全负数组中遗漏允许返回零的空选择。
- 使用 32 位整数保存大量副本的总贡献，或提前取模再比较，都会破坏真实最大值的计算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 先在一份或两份拼接数组上求最大子段，更多重复部分的贡献由整段总和决定。 |
| 918. 环形子数组的最大和 | 中等 | 同样需要考虑跨首尾连接，但环形题最多绕一次，本题可以包含多份完整数组。 |