LeetCode 918. 环形子数组的最大和
目录
题目描述
题意分析
数组首尾相接成环，要在环上取一段连续且非空的元素使和最大。与线性版本的唯一区别是：这段元素允许从数组尾部绕回头部，例如在
[5,-3,5]上可以取到末尾的5和开头的5，答案是 10。同时题目明确规定每个下标最多被取一次，也就是绕回来之后不能继续往前吃掉已经取过的元素。
元素可以是负数（范围
-3 * 10^4到3 * 10^4），这意味着"和越加越大"的直觉不成立，任何依赖单调性的窗口做法都不适用；而 $n$ 最大到 $3 \times 10^4$，把数组复制一份变成长度 $2n$ 再暴力枚举所有起点终点是 $O(n^2)$，在这个规模下已经很危险，约束在提示我们要找一个一次扫描就能出结果的做法。
所有元素都可能是负数，这时最优解只能是"损失最小的那一个元素"，而不是空集——非空的要求让这种全负输入成为必须单独讨论的边界。除此之外还要注意长度为 1 的数组，此时唯一的答案就是那个元素本身。
解法：最大子数组和 + 最小子数组和
核心思路
问题关键： 环形连续子数组只有两种形态：不跨首尾、跨首尾。前者就是普通最大子数组和；后者的补集是原数组中间的一段连续子数组。
为什么用双 Kadane： 设数组总和为
total。不跨首尾的候选是最大子数组和maxSum；跨首尾等价于挖掉一段和最小的中间区间，候选为total - minSum。两个极值都能一趟计算。状态与不变量：
curMax和curMin分别表示“必须以当前元素结尾”的最大和、最小和；每步只需在“接上前一段”和“从当前元素重开”之间选择。maxSum和minSum记录截至当前的全局极值。正确性： 两类子数组覆盖了全部可能，分别取到最优值后再取较大者就是全局最优。唯一例外是全负数组：此时
minSum == total，total - minSum等于 0，实际表示删掉整个数组。题目要求子数组非空，因此必须返回maxSum。
解题步骤
- 初始化总和、两组当前状态以及两组全局极值；全局极值用
nums[0]初始化，保证答案非空。- 扫描每个
num，累加total，同时更新以num结尾的最大和、最小和及其全局极值。- 若
maxSum < 0，说明所有元素都为负，直接返回maxSum。- 否则返回
max(maxSum, total - minSum)。口述示例：
[5,-3,5]的total = 7、maxSum = 7、minSum = -3，跨首尾候选为7 - (-3) = 10，所以答案是 10。边界反例：
[-3,-2,-3]中total - minSum = 0，它表示把整个数组删光，并非合法子数组；正确答案是maxSum = -2。
代码实现
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)$，只维护若干标量。
关键点总结
- 环形区间按“是否跨首尾”分类，跨首尾解用补集转化。
- Kadane 的局部状态必须限定“以当前元素结尾”，不能与全局极值混淆。
- 最大和、最小和可在同一趟扫描中对称维护。
- 面试时要主动说明全负特判：它排除了“挖掉整个数组”的非法空集。
易错点总结
- 漏掉全负特判：
[-3,-2,-3]会错返空集的和 0，而非 -2。- 将全局极值初始化为 0：
[-1]会被错判为 0。- 把跨首尾候选写成
total - maxSum；应当减去最小连续子数组。- 复制两份数组后直接跑 Kadane：若不限制区间长度，同一下标可能被取两次。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 线性版本，只需要一套 Kadane 状态，没有接缝和补集讨论 |
| 剑指 Offer 42. 连续子数组的最大和 | 简单 | 与 53 同题，适合用来把"必须以当前元素结尾"的状态定义练熟 |
| 面试题 16.17. 连续数列 | 简单 | 同样是线性 Kadane，常被用来考察全负数组的边界处理 |
| 1186. 删除一次得到子数组最大和 | 中等 | 状态多出"是否已删除一个元素"这一维，转移从一条变成两条 |
| 1191. K 次串联后最大子数组之和 | 中等 | 数组重复 K 次而非成环，要按总和正负分类并对中间段做整段累加 |