环形子数组的最大和，第一次在力扣上看到这道题的时候，我其实没太当回事。毕竟“最大子数组和”几乎是动态规划入门必刷题，换个环形外壳能难到哪去？结果真被教做人了：普通版本的代码能一遍过，环形版本我连续交了三发，不是全负数用例没处理好，就是最终答案差一个边界。后来把这类题整理进算法训练营讲义时我才发现，环形子数组的最大和考察的根本不是“会不会写 Kadane”，而是“懂不懂状态到底在描述什么”。这篇文章就围绕这道题，把从暴力、优化到边界处理的完整链路讲清楚，适合准备面试、刷题进度的同学，也适合想把动态规划原理真正吃透的读者。
先看一眼题面：给定一个长度为 n 的整数数组，把它看成一个首尾相接的环形数组，求所有连续子数组中和的最大值。子数组至少包含一个元素，n 的范围通常到 10^5 级别，所以 O(n^2) 基本没戏。这里有个反直觉的地方：普通数组求最大子数组和只用一次线性扫描，为什么换成环形就要重新设计解法？答案就藏在“首尾相接”这四个字里。
1. 先分清两种子数组形态，别急着写代码
1.1 普通最大子数组和：Kadane 算法的底子
普通版本的问题很简单：在一个数组中找一段连续区间，让区间和最大。最经典的解法是 Kadane 算法，核心状态转移只有一行：
cur = max(num, cur + num)我最早学这行代码的时候，只觉得它是“贪心”，后来才发现它是“状态定义”的胜利。维护一个变量 cur，表示以当前元素结尾的最大子数组和，那么每一轮只有两个选择：要么把当前元素接到前一个子数组后面，形成更长的连续段；要么抛弃前面所有累赘，从当前元素重新开始。取个 max，就是最优决策。
配合另一个变量 best，记录历史所有 cur 的最大值，最后返回 best，一次遍历搞定。这个算法的优点是时间 O(n)、空间 O(1)，而且代码短到不容易出错。很多人刷题刷多了，Kadane 几乎是肌肉记忆，但我建议还是要把“为什么取 max 而不是一直累加”想明白，因为后面环形版本的坑，恰恰出在这种“以为懂了”的状态上。
1.2 环形到底改变了什么
普通数组是直线，子数组只能从头到尾顺着选；环形数组相当于把数组两端粘在一起，允许你从尾部某个位置开始，绕过头走到头部某个位置结束。比如数组 [5, -3, 5]，普通最大子数组和是 5，但环形情况下，可以取末尾的 5 和开头的 5，中间跨过“边界”，答案是 10。这种“跨边界”的子数组，在普通数组里是选不出来的。
很多人第一反应是：既然需要跨边界，那把数组复制一倍接到后面，再用普通 Kadane 不就行了？这个思路方向是对的，但有个隐藏陷阱：复制一倍后跑普通 Kadane，可能会选出长度超过 n 的子数组。比如 [5, -3, 5] 复制成 [5, -3, 5, 5, -3, 5]，普通 Kadane 会把中间的 5、-3、5、5、-3、5 全部加起来得到 14，等于把原数组绕了一圈还多，这在环形数组里是不合法的。子数组长度最多只能等于 n，所以“复制数组 + 普通 Kadane”不能直接用。
环形子数组只有两种形态：一种老老实实待在中间，不跨越首尾边界，本质就是普通最大子数组；另一种跨越了边界，此时它一定可以被描述成“数组总和的某个部分”。这个视角非常关键，它直接推导出最优解法。
2. 解法演进：从暴力到最优的必经路径
2.1 暴力枚举为什么不行
先算一笔复杂度账。最容易想到的做法是枚举起点和终点，把原数组当作环来取模访问，复杂度 O(n^2)。当 n = 10^5 时，最坏情况要执行 10^10 次运算，这在绝大多数判题环境下都是超时的。另一种“复制数组 + 双重循环”看起来简单，空间变成 O(n)，时间还是 O(n^2)，本质上没有改善。
暴力存在的意义不是给你 AC，而是帮你验证思路。我自己写题时有个习惯：拿到新题先想暴力，再用暴力输出结果和优化版本对拍。环形子数组的最大和尤其适合对拍，因为边界情况多，纯靠人肉推容易漏。保留一个 O(n^2) 的暴力函数作为“裁判”，是性价比很高的调试手段。
2.2 双情况法的公式怎么来的
把环形子数组分成两类考虑，就能绕开环形判题：
- 情况一：最大子数组没有跨越首尾边界，它落在数组内部的某个区间。
- 情况二：最大子数组跨越了首尾边界，比如 [5, -3, 5] 中的答案 10。
情况一直接用 Kadane 算。情况二怎么算？可以换个角度想：跨越边界的子数组，在数组内部被“舍弃”的恰恰是一段连续的子数组。比如 [5, -3, 5] 跨越边界取“末尾 5 + 开头 5”，中间被舍弃的就是 [-3]。要让跨边界的子数组和最大，等价于让这段被舍弃的连续子数组和最小。
于是情况二的最大值就是：数组总和 total - 最小子数组和。最小子数组和可以用 Kadane 的镜像版本求，把“最大”改成“最小”：
cur_min = min(num, cur_min + num)最后答案取两种情况的最大值：
ans = max(best_max, total - best_min)这个公式看起来简单，但有个前提：被舍弃的子数组不能是“整个数组”，否则跨边界的子数组就变成空数组了。空数组在题目里是不允许的。这个前提正好引出全负数用例的经典陷阱，后面专门讲。
2.3 为什么不能直接复制数组跑 Kadane：一个反例
上面提到复制数组会有问题，这里用一个更细的例子说明。假设数组是 [5, -3, 5, 1]，复制成 [5, -3, 5, 1, 5, -3, 5, 1]，普通 Kadane 可能选出一段长度 4 的子数组，也可能选出一段长度超过 4 的子数组，因为复制后“没有长度限制”。
有人会说：那我限制长度不超过 n 不就行了？确实可以，但那就不是简单的 Kadane 了，需要借助前缀和 + 单调队列，维护一个长度不超过 n 的窗口内的最大子数组和。这是另一种解法，我在第 5 部分会展开讲。双情况法的优势在于：不复制数组、不加长度限制，只需要跑两次线性遍历，代码更好写，推导也更符合直觉。
要提醒的是，“取两种情况最大值”的方法只适用于“子数组不允许为空”的设定。如果题目允许空子数组，那你得把公式改成 max(best_max, total - best_min, 0) 或者类似形式。刷题时一定先读清楚题面，很多边界错误其实是题意理解偏差。
3. 核心细节与代码实现：把公式变成能 AC 的代码
3.1 Python 实现与逐行注释
直接看我实际提交通过的版本，Python 代码很短，但每一行都有讲究：
def max_subarray_sum_circular(nums): if not nums: return 0 total = sum(nums) # Kadane：最大子数组和 cur_max = 0 best_max = float('-inf') for x in nums: cur_max = max(x, cur_max + x) best_max = max(best_max, cur_max) # 镜像 Kadane：最小子数组和 cur_min = 0 best_min = float('inf') for x in nums: cur_min = min(x, cur_min + x) best_min = min(best_min, cur_min) # 如果最大子数组和小于 0，说明全是负数，直接返回最大元素 if best_max < 0: return max(nums) return max(best_max, total - best_min)这里有两个关键点。第一，cur_max 和 cur_min 的初始值。常见写法是初始化为 0，因为空数组的和是 0，Kadane 的“重新开始”选择天然包含了“从 0 开始”的语义。但 best_max 必须初始化为负无穷，否则全负数数组会被初始值 0 带偏，导致结果变成 0 而不是真正的负数最大值。第二，最后那个 if best_max < 0 的判断，是整个环形版本的点睛之笔。它的作用是处理“全是负数”的极端场景，此时 best_max 本身就是正确答案，不需要再和 total - best_min 比较。
3.2 全为负数时为什么答案不是 0
拿 [-3, -2, -1] 举例。普通 Kadane 得到 best_max = -1，这是正确答案，因为子数组至少要取一个元素。再看看 total - best_min：数组总和是 -6，最小子数组和是整个数组 -6，算出来 total - best_min = 0。如果直接取 max(best_max, total - best_min)，就会得到 0，而题目要求子数组非空，正确答案是 -1。
为什么会出现这种情况？因为最小子数组和恰好等于整个数组的和，意味着如果要“舍弃”这一段，剩下的部分就是空数组。环形子数组不能为空，所以这种情况不能套用情况二。判别方法就是看 best_max 是否小于 0：如果最大子数组和都小于 0，说明数组里所有元素都是负数，此时任何一个非空子数组都是负数，不如直接取单个最大元素。这种情况直接返回 max(nums) 即可。
我在训练营里见过不少同学在这里翻车：不是没加 if，就是加了 if 但把 best_max 初始化为 0，导致全负数数组在进入 if 前就已经算错。把这两件事分开记：best_max 初始值影响 Kadane 本身，if 判断影响环形部分的公式，缺一不可。
3.3 其他语言的实现差异与坑
换到 C++ 或 Java，核心逻辑一模一样，但要额外注意两个语言层面的问题。
第一个是整数溢出。如果数组元素范围和 n 都很大，total、cur_max、cur_min 这些变量可能超过 int 的表示范围。C++ 里建议直接用 long long，Java 里用 long，避免求和过程中悄悄溢出变成负数，然后在比较时产生诡异结果。我见过有人用 int 写成 total - best_min，溢出后反而得到一个很大的正数，答案完全错乱，排查半天才意识到是类型问题。
第二个是语言库函数的边界。C++ 的 std::max 要求两个参数类型一致，如果 best_max 是 long long，传入 max(nums) 就会因为类型不一致编译报错，需要显式转换。Java 里 Collections.max 和数组处理方式也不同。这些小问题不影响算法本身，但在白板面试时很影响观感，建议提前准备好自己最熟语言的模板版。
下面是 C++ 版本参考：
int maxSubarraySumCircular(vector<int>& nums) { int n = nums.size(); long long total = 0; for (int x : nums) total += x; long long curMax = 0, bestMax = LLONG_MIN; long long curMin = 0, bestMin = LLONG_MAX; for (int x : nums) { curMax = max((long long)x, curMax + x); bestMax = max(bestMax, curMax); curMin = min((long long)x, curMin + x); bestMin = min(bestMin, curMin); } if (bestMax < 0) { return *max_element(nums.begin(), nums.end()); } return max(bestMax, total - bestMin); }这里我把 curMax 和 curMin 放在同一个循环里更新，省一次遍历，但逻辑上还是两个独立的 Kadane。要注意的是，如果你在同一循环里更新 curMax 和 curMin，千万不要让它们互相干扰，否则边界会乱。
4. 常见错误与排查技巧实录
4.1 高频翻车场景和排查思路
我把自己和学员踩过的坑汇总成一张速查表，按出现频率排序：
| 症状 | 可能原因 | 排查方法 |
|---|---|---|
| 全负数数组返回 0 | best_max 初始化为 0，或缺少 best_max < 0 判断 | 打印 best_max，检查是否被初始值污染 |
| 答案总比预期大 | 复制数组后直接跑普通 Kadane，子数组长度超过 n | 改用双情况法，或加长度限制 |
| 结果正好少了一个元素 | 最小子数组和计算错误，把空数组也算进去了 | 检查 cur_min 初始值，确认每个元素都被访问 |
| 溢出导致的随机错误 | 使用了 int 而数组求和超范围 | 换成 long long，打印 total 验证 |
| 只有一个元素时答案不对 | 全负数判断逻辑写反 | 单独跑 [5] 和 [-5] 两个用例 |
排查这类问题，最好的工具不是脑补，而是对拍。写一个暴力版本，用随机小数组反复比较两种结果，一旦不一致就缩小数组规模，人工推演。环形数组的随机测试用例很容易暴露边界问题，我实测 100 组随机数据不到几秒就能覆盖绝大多数坑。
4.2 测试用例速查表与验证顺序
下面这组用例是我每次写完代码必跑的，按从简单到复杂的顺序：
| 输入数组 | 预期结果 | 验证点 |
|---|---|---|
| [5] | 5 | 长度 1 的基础情况 |
| [-5] | -5 | 单元素全负数 |
| [-3, -2, -1] | -1 | 全负数，防止返回 0 |
| [5, -3, 5] | 10 | 跨边界的经典用例 |
| [1, -2, 3, -2] | 3 | 最优解在中间，不跨边界 |
| [8, -1, 6, -9, 2] | 14 | 跨边界和普通段竞争 |
| [1, 2, 3] | 6 | 全正数，答案就是总和 |
特别注意最后一组全正数用例。此时 best_max = total = 6，而 best_min 可能是数组中的单个最小元素 1，total - best_min = 5，最后 max 取到 6。如果你发现代码在这种用例返回 total - best_min，那说明 min 的计算没有考虑“从正数开头会立即重来”的规则，需要回头检查 cur_min 的转移式。
4.3 面试官考这道题时真正想看什么
环形子数组的最大和在算法竞赛里不算难题，但面试官喜欢用它做“一题多考”。第一层考 Kadane 本身，确认候选人理解状态转移；第二层考环形抽象，确认候选人能不能把“跨越边界”转化为“总和减最小段”；第三层考边界条件，全负数这种用例很容易区分“背结论”和“真理解”。
我给你的建议是，面试时先慢下来，画一个环形图，把两种子数组形态讲清楚，再动手写代码。面试官通常更在意思路推导，而不是你背得多熟。写代码时先写 Kadane 部分，再补全负数判断，最后再合并答案，这样即使时间不够，也能拿到大部分分数。还有个小技巧：主动问面试官“子数组是否允许为空”，这个问题比答案本身更显专业。
复杂度分析也别忽略：双情况法的时间复杂度是 O(n)，空间复杂度是 O(1)。有的面试官会追问，能不能不用 if 判断做到全负数也正确？可以，但代价是公式变得更复杂，实际工程意义不大，白板场景推荐保留 if 判断，代码更清晰。
5. 延伸：环形子数组还能怎么考
5.1 换成滑动窗口 + 单调队列的解法
除了双情况法，环形子数组还有一个通用解法：复制数组成两倍长度，再用“单调队列 + 前缀和”维护长度不超过 n 的窗口内最大子数组和。这个思路能处理“允许空子数组”或“限定子数组长度不超过 k”的变种，适用范围更广。核心代码结构如下：
from collections import deque def max_subarray_sum_circular_with_queue(nums): n = len(nums) arr = nums + nums prefix = [0] for x in arr: prefix.append(prefix[-1] + x) q = deque([0]) ans = float('-inf') for j in range(1, len(prefix)): while q and q[0] < j - n: q.popleft() if q: ans = max(ans, prefix[j] - prefix[q[0]]) while q and prefix[q[-1]] >= prefix[j]: q.pop() q.append(j) return ans这个版本的时间也是 O(n)，但空间是 O(n)。它比双情况法代码长，理解难度也更高，好处是统一处理了“长度限制”和“环形”两个约束。如果你刷题遇到类似的“环形滑动窗口”题，比如环形最大平均值、环形子数组恰好 k 个元素，单调队列方案更通用。我个人建议：作为面试主打解法，双情况法优先；作为延伸理解，单调队列值得掌握，因为它能解决一类问题而不是一道题。
5.2 从一维到二维：最大子矩阵的环形扩展
如果把一维数组换成二维矩阵，问题就变成“环形矩阵的最大子矩阵和”。这个升级版可以先对列做前缀和压缩，把二维问题压成一维，然后对每一行组合跑一遍环形子数组的最大和。复杂度和行数、列数的乘积相关，属于比较硬核的进阶题。这里不展开代码，但核心思想还是“压缩维度 + 环形处理”，和今天讲的题一脉相承。
所以你看，环形子数组的最大和这道题虽然本身难度不高，但它像一个小枢纽，一头连着动态规划经典模型，一头连着滑动窗口、前缀和、二维压缩这些进阶技巧。把它吃透，收获的不只是一个 AC 记录，而是一整套“环形数组”类问题的解题套路。
5.3 变种题：允许空子数组与固定长度子数组
最后补充两个常见变种。第一个变种是“允许空子数组”，这时双情况法的公式要改成 max(best_max, total - best_min, 0)，并且全负数时答案就是 0。第二个变种是“子数组长度必须恰好为 k”，这个直接用双情况法解决不了，得靠单调队列或定长滑动窗口，因为你需要约束被舍弃段的长度不能超过 n - k。
这两种变种在竞赛题库里经常出现，面试现场倒不一定考，但如果你平时刷题有余力，建议顺手把单调队列版本也敲一遍。我自己的体验是，第一次写单调队列版本花了近一个小时，各种下标错误；搞清楚之后，再遇到“长度限制 + 数组”的题，基本十分钟内能写完。这种能力是会迁移的，属于典型的“一道题功力远超一道题”的类型。
与数据规模有关的经验总结
刷这类题的时候，我习惯先看一眼数据范围再决定策略。n 小于 100，暴力随便写，对拍也方便；n 到 10^5，必须 O(n)；n 到 10^6，要小心 Python 在循环里的常数开销，尽量少用切片和冗余数组；如果数值范围特别大，注意 long long 和 Python 大整数的差异。数据规模和写代码的习惯是长期磨合出来的，见得多了自然就有手感。
回到最开始那个让我翻车的全负数用例。后来我把这道题作为训练营的必讲题目，每一期都能遇到学员在同一个地方卡住。这个现象其实说明，算法题的难点往往不在核心公式，而在边界意识的完整性。普通 Kadane 不会遇到“空子数组”的问题，因为大家都默认至少选一个元素；环形版本一旦用公式，空子数组就被“制造”出来，于是必须加判断。理解了这个因果链，你才算真正掌握了这道题。
如果让我给一个练习建议，那就是把双情况法和单调队列版本都各写一遍，然后互相随机对拍 1000 组数据。不要急着背代码，先用小例子把“为什么答案等于 max(best_max, total - best_min)”讲给自己听，讲得通，代码怎么写都不会偏。这个方法帮助我解决过很多类似的“环形 + 动态规划”题目，希望对你也有效。
