LeetCode 918. 环形子数组的最大和
题目描述
题意分析
在首尾相接的数组中选择一个非空连续子数组，使元素之和最大。可以从末尾继续走到开头，但每个原下标最多使用一次，因此所选长度不能超过数组长度。
返回最大和即可，不需要返回下标。选择可以是普通线性区间，也可以跨越首尾，甚至包含整个数组；全为负数时也必须至少选择一个元素，不能以空数组的零作为答案。
解法：最大子数组和 + 最小子数组和
核心思路
[!blue]
按是否跨越首尾分两类。不跨越的选择就是普通最大子数组和
maxSum；跨越的选择由原数组的一段后缀和一段前缀组成，中间没有选择的部分是一个连续区间。总和total固定，要让保留部分最大，就应让被排除的连续区间和minSum最小，候选为total - minSum。用两组 Kadane 状态在一趟扫描中求出它们。
curMax表示必须以当前元素结尾的最大和：要么接在上一位置的最佳结尾区间后，要么只选当前项，所以取max(curMax + num, num)；curMin同理取min(curMin + num, num)。再分别用这两个局部值更新全局最大、最小值。局部状态必须包含当前项，才能表示连续区间；全局状态则记录到目前为止任意结尾的最优值。全局最大和最小都从首项初始化，避免将空区间混入。局部初值为零仅用于首次转移，第一轮两种候选都会得到首项本身。
取补集有一个边界：最小子数组可能是整个数组，此时
total - minSum得到空集的零。若maxSum < 0，说明所有元素均为负，必须直接返回最大的单项，也就是普通maxSum。非全负时，如果最大和为正，虚假的空集零不会胜过它；如果最大和为零，数组中必有零，已经存在和为零的合法非空区间，因此比较结果仍正确。最小区间贴着某一端时，其非空补集就是普通区间，也属于合法候选；整段全选则由普通最大子数组和覆盖。
最后在非全负情况下取
max(maxSum, total - minSum)，便同时覆盖普通区间和跨首尾区间，且不会重复使用原位置。
解题步骤
- 将
maxSum、minSum初始化为首项，total、curMax、curMin初始化为零。- 遍历每个元素并累加总和，分别计算以当前项结尾的最大和、最小和。
- 用局部状态更新对应的全局最大、最小连续区间和。
- 若
maxSum < 0，返回maxSum；否则返回它与total - minSum的较大值。
代码实现
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int total = 0;
int curMax = 0;
int curMin = 0;
int maxSum = nums[0];
int minSum = nums[0];
for (int num : nums) {
total += num;
// 局部状态必须以当前项结束，可延续也可重新开始
curMax = Math.max(curMax + num, num);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(curMin + num, num);
minSum = Math.min(minSum, curMin);
}
// 全负时总和减最小和对应空段，必须排除
if (maxSum < 0) {
return maxSum;
}
return Math.max(maxSum, total - minSum);
}
}
func maxSubarraySumCircular(nums []int) int {
total, curMax, curMin := 0, 0, 0
maxSum, minSum := nums[0], nums[0]
for _, num := range nums {
total += num
// 局部状态必须以当前项结束，可延续也可重新开始
curMax = maxCircular(curMax+num, num)
maxSum = maxCircular(maxSum, curMax)
curMin = minCircular(curMin+num, num)
minSum = minCircular(minSum, curMin)
}
// 全负时总和减最小和对应空段，必须排除
if maxSum < 0 {
return maxSum
}
return maxCircular(maxSum, total-minSum)
}
func maxCircular(a, b int) int {
if a > b {
return a
}
return b
}
func minCircular(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n)$，一趟扫描。
- 空间复杂度：$O(1)$，两组局部及全局状态。
关键点总结
[!green]
- 跨首尾的连续选择，其未选部分是普通连续区间，因此可用总和减最小区间和。
- 局部状态必须以当前项结尾，全局状态可以在任意位置结束，两者职责不同。
- 全负输入必须排除删除全部元素得到的空补集；含零时零本身就是合法非空答案。
- 每次转移只需上一轮局部状态，不必保存整张数组。
易错点总结
[!yellow]
- 全局最大值初始化为零会把全负输入误判为空集，应从首项开始。
- 环形候选是总和减最小和，减去最大和与求保留部分最大值的目标相反。
- 未处理全负边界，会用删除整段后的非法零替代正确负数答案。
- 不能直接把数组拼接两遍后求无限制最大子数组和，否则可能重复使用原下标。
- 用全局最优替代局部结尾状态参与转移，可能拼接不连续的区间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 先求普通最大子数组，再处理跨首尾的情况，跨界结果可由总和减最小连续段得到。 |
| 152. 乘积最大子数组 | 中等 | 两题都涉及最大与最小状态，本题最小和用于补集，乘积题则因负数改变大小关系。 |
| 1186. 删除一次得到子数组最大和 | 中等 | 维护以当前位置结尾的最优连续区间；本题同时计算最小区间和处理首尾相接，该题增加已经删除一次的状态。 |
| 1567. 乘积为正数的最长子数组长度 | 中等 | 维护以当前位置结尾的最优连续区间；本题同时计算最小区间和处理首尾相接，该题只维护正负乘积对应的最长长度。 |