1. 先搞懂环形子数组和普通子数组差在哪LeetCode 918 这道题本质上是在 53 题“最大子数组和”的基础上把数组从一条直线首尾相连变成了一个环。很多人第一次做的时候第一反应是“这不就多了一种跨越边界的情况吗”然后直接套 Kadane 算法结果发现答案不对卡在 [5, -3, 5] 这种用例上——普通数组的最大子数组和是 5但环形数组能取到 [5, 5]一个在开头一个在结尾首尾相接答案应该是 10。这就是环形子数组和普通子数组最核心的区别子数组的起点和终点不再受数组边界的限制。换成人话说普通数组只能从某个位置开始、往后连续取环形数组可以从任意位置开始绕一圈回到起点之前的位置只要总长度不超过 n。这个“长度不超过 n”的约束也是后面两种解法里反复出现的重点因为如果允许取整个数组再绕一圈那就等于可以无限累加没有意义了。1.1 暴力枚举是怎么做的先看最直观的做法。枚举所有可能的子数组起点 i然后从 i 开始往后累加最多累加 n 个元素因为环形数组里连续子数组的长度不可能超过 n用取模的方式模拟绕圈。这样两重循环外层枚举起点内层枚举长度时间复杂度 O(n^2)。代码写出来倒是很简单def maxSubarraySumCircular(nums): n len(nums) ans float(-inf) for i in range(n): cur 0 for length in range(1, n 1): cur nums[(i length - 1) % n] ans max(ans, cur) return ans这个解法在 LeetCode 上直接超时因为 n 可以达到 3 * 10^4O(n^2) 是 9 亿次操作任何语言都扛不住。但它最大的价值在于帮我们建立了对题目的正确认知环形子数组本质上就是从某个点开始、顺时针连续取一段长度不超过 n。1.2 把环形问题拆成两种形态暴力解法虽然慢但给我们提供了一个重要的分类视角。任意一个环形子数组按照是否跨越了原数组的末尾边界可以分成两类第一类是不跨越边界的普通子数组比如 [1, -2, 3, -2] 里的 [3]它和 53 题完全一样直接在原数组上用 Kadane 算法求最大子数组和就行。第二类是跨越边界的环形子数组比如 [5, -3, 5] 里的 [5, 5]由末尾的 5 和开头的 5 拼成。这类子数组有一个非常优美的补集关系如果整个数组的总和是 total一个跨越边界的最大子数组等于 total 减去“在数组中间去掉的那一段连续子数组的和”。因为环形数组取一段剩下的就是另一段连续的部分取首尾相连的一段剩下的一定是中间连续的一段。于是核心问题就变成了求数组中连续子数组的最小和。这个转换是整个题目的灵魂解法二就是基于这个思想做的解法一则是换了一个角度用双倍数组把环形问题压平成线性问题。两条路最终都能到达终点但适用场景和坑位完全不同。2. 解法一双倍数组 前缀和 单调队列这个解法的思路非常工程化一句话概括把环形数组复制一份接在后面得到长度为 2n 的线性数组然后用一个固定最大长度 n 的滑动窗口在这个线性数组里找最大子数组和。2.1 为什么数组翻倍就能解决环形设想一下环形数组里的任意一个合法子数组如果把数组从某个位置切断并展平这个子数组可能因为跨越切口而断成两截。但如果把数组复制一份拼接起来任何一个长度不超过 n 的连续子数组一定能在这个 2n 长度的数组里找到完整的一段。比如 [5, -3, 5] 中的 [5, 5]在 [5, -3, 5, 5, -3, 5] 里就是第 3 到第 4 个元素连续且完整。翻倍之后问题就变成了在一个长度为 2n 的数组里找到长度不超过 n 的连续子数组的最大和。注意这里有个“长度不超过 n”的限制不能直接在整个 2n 数组上跑 Kadane因为那样可能取到长度超过 n 的子数组比如把所有 6 个元素都取了那就相当于绕了不止一圈。2.2 单调队列到底在维护什么要在滑动窗口内快速求最大子数组和经典的“前缀和 单调队列”组合是首选。前缀和数组 prefix 的定义是 prefix[i] sum(arr[0..i-1])这样任意区间 [j, i-1] 的和就是 prefix[i] - prefix[j]。那么固定右端点 i以 i-1 结尾的最大子数组和就是 prefix[i] - min(prefix[j])其中 j 必须落在窗口内也就是 i - j n。换句话说我们每次要拿到窗口内前缀和最小的那个位置。单调队列在这里扮演的角色就是“滑动窗口内最小值”的维护器。队列里存的是下标从队首到队尾对应的 prefix 值严格递增这样队首永远是当前窗口内前缀和最小的位置。每次 i 向右移动时先移除所有使得窗口长度超过 n 的过期下标i - q[0] n 就弹出队首然后用当前前缀和 prefix[i] 更新答案再把 prefix[i] 从队尾插入并维持单调性。有人可能会问为什么不能直接在窗口内跑 Kadane因为那样每次窗口滑动都要重新计算复杂度退化。而前缀和配合单调队列每次操作均摊 O(1)整体 O(n)。2.3 完整代码与复杂度分析from collections import deque def maxSubarraySumCircular(nums): n len(nums) arr nums nums # 双倍数组 prefix [0] * (2 * n 1) for i in range(2 * n): prefix[i 1] prefix[i] arr[i] q deque([0]) # 存下标对应前缀和单调递增 ans float(-inf) for i in range(1, 2 * n 1): # 保证窗口长度不超过 n窗口起点是 q[0]终点是 i-1 while q and i - q[0] n: q.popleft() # 以 i-1 结尾的最大子数组和 ans max(ans, prefix[i] - prefix[q[0]]) # 维持单调队列单调性当前前缀和下标入队 while q and prefix[q[-1]] prefix[i]: q.pop() q.append(i) return ans时间复杂度 O(n)双倍数组只是常数 2空间复杂度 O(n)主要花在 prefix 数组上。实测这套代码在 LeetCode 上运行时间稳定在 200ms 以内Python3内存占用约 17MB。这个解法的优点是思路直白不需要分类讨论只要理解了“滑动窗口 最小前缀和”就能写出来。缺点是代码稍微长一点而且单独写一个单调队列对不熟悉的人不太友好。3. 解法二Kadane 变体更推荐面试写解法二是基于补集思想做的代码更短也更接近面试官想听到的推理过程。核心公式是答案 max(最大非环子数组和, 总和 - 最小非环子数组和)其中“最大非环子数组和”就是标准 Kadane 算法跑一遍的结果“最小非环子数组和”则是把 Kadane 的 max 换成 min求整个数组里和最小的连续子数组。3.1 最大非环子数组和标准 KadaneKadane 算法的核心是动态规划。定义 dp[i] 为以 nums[i] 结尾的最大子数组和则转移方程为dp[i] max(nums[i], dp[i-1] nums[i])意思是要么从 nums[i] 重新开始一段要么把 nums[i] 接到之前的最优段后面。最终结果 dp 数组里的最大值就是答案。代码习惯上用一个变量滚动更新不占用额外数组。max_cur max_best nums[0] for i in range(1, n): max_cur max(nums[i], max_cur nums[i]) max_best max(max_best, max_cur)3.2 最小子数组和对称写法最小子数组和完全同理把 max 换成 min 即可。dp_min[i] min(nums[i], dp_min[i-1] nums[i])表示以 nums[i] 结尾的最小子数组和。min_cur min_best nums[0] for i in range(1, n): min_cur min(nums[i], min_cur nums[i]) min_best min(min_best, min_cur)一个很自然的疑问是为什么“总和 - 最小子数组和”一定对应一个合法的环形子数组我个人的理解方式是把环形子数组想成在环上取了一段那剩下没取的部分一定是环上另一段连续部分而“总和 - 最小段”就等价于“最大可取得段”。比如 [5, -3, 5]总和是 7最小子段是 [-3]两者相减等于 10正好是我们要的 [5, 5]。这个转化不需要证明画个环形图一眼就懂。3.3 全负数边界最大的坑如果数组里全是负数比如 [-2, -3, -1]最大非环子数组和是 -1最小非环子数组和是整个数组 -6总和是 -6于是“总和 - 最小子数组和”等于 0这明显是错的——环形子数组不能为空不能返回 0。为什么会出现这个错误因为“总和 - 最小子数组和”在最小子数组等于整个数组时计算结果是 0对应空集。只有全负数时整个数组才是最小子数组所以这个分支会算出空集。解决办法是特判如果 max_best 0说明所有元素都是负数直接返回 max_best此时它等于最大单个元素。因为任何长度大于 1 的连续子数组只会更小所以答案就是最大的那个负数。if max_best 0: return max_best这个判断必须放在最后不能写成“if total min_best”这种形式因为当数组里恰好有 0 时total min_best 也可能成立但此时答案可能不是负数。比如 [0, -1, -2]总和是 -3min_best 是 -3total - min_best 0但实际答案应该是 0取子数组 [0]所以单靠 total min_best 判断不够准确用 max_best 0 判断最稳妥。3.4 完整代码与复杂度分析def maxSubarraySumCircular(nums): n len(nums) total sum(nums) max_cur max_best nums[0] min_cur min_best nums[0] for i in range(1, n): max_cur max(nums[i], max_cur nums[i]) max_best max(max_best, max_cur) min_cur min(nums[i], min_cur nums[i]) min_best min(min_best, min_cur) # 全负数任何跨环子数组不可能比单个最大元素更大 if max_best 0: return max_best return max(max_best, total - min_best)时间复杂度 O(n)空间复杂度 O(1)只用了几个变量。代码量是两种解法里最少的而且不需要额外的数据结构。4. 两种解法对比与选型建议很多人关心这两种解法到底该选哪种我直接把对比列出来维度解法一双倍数组 前缀和 单调队列解法二Kadane 变体时间复杂度O(n)O(n)空间复杂度O(n)O(1)代码量偏长需要额外处理双倍数组和队列很短一个循环搞定易错点窗口长度限制、队列过期判断全负数特判思考路径压平环形转化为线性滑窗补集思想分类讨论面试友好度中需要解释单调队列原理高推理过程很自然我的建议是如果是面试优先讲解法二。原因是它的推导过程非常清晰从“环形问题拆成不跨环和跨环两类”到“跨环等于总和减最小子数组”每一步都有明确的逻辑支撑面试官很容易跟得上。而且代码短写完不容易有问题全负数特判还能展示你的严谨性。解法一的适用场景是当你对单调队列很熟或者面试官明确要求不能用分类讨论、必须用统一的滑窗思路时它可以作为备选。实际上我在面试中被追问过“如果还要支持动态修改数组元素怎么办”这时候解法一的思路就更有扩展性因为前缀和结构容易改造成线段树或树状数组。如果是在 LeetCode 上刷题我建议两种都写一遍。解法二帮你记住核心逻辑解法一帮你复习单调队列。两个都动手写过之后下次遇到“环形数组 最大子数组”这类变体题基本上都能很快定位到正确解法。5. 刷题与面试中的常见坑5.1 四个必测的边界用例我在提交之前一定会跑这组用例命中率极高输入预期输出说明[1, -2, 3, -2]3常见混合正负[5, -3, 5]10跨环边界关键用例[-2, -3, -1]-1全负数特判[0, 1, 2]3含 0不需要跨环其中 [5, -3, 5] 是检验“是否真正处理了跨环情况”的试金石很多错误实现会返回 5。全负数用例则能检验你是否考虑到了空集的陷阱。5.2 为什么不能直接套普通滑窗有人想既然解法一用了双倍数组和滑动窗口那能不能直接维护一个长度为 n 的滑动窗口窗口内跑 Kadane理论上可以但每次窗口移动时重新计算窗口内最大子数组和是 O(n) 的整体变成 O(n^2)。这也是为什么需要前缀和 单调队列来把单次查询降到 O(1) 的原因。还有一个常见的误区直接在双倍数组上跑标准 Kadane不管长度限制。比如 [5, -3, 5] 的双倍数组是 [5, -3, 5, 5, -3, 5]标准 Kadane 会算出 17整个数组求和因为 [5, -3, 5, 5, -3, 5] 全加起来等于 17。但环形数组的合法子数组长度不能超过 3所以这个结果是错的。这也是为什么解法一里窗口长度限制是解题关键不是可选项。5.3 Java/C 里的整型溢出细节如果你用 Java 或 C 写解法二total 可能达到 3 * 10^9 级别n 最大 3 * 10^4每个元素最大 3 * 10^4总和最大 9 * 10^8还没到 int 上限 2.1 * 10^9但接近了。更危险的是 prefix 数组在解法一里2n 长度下的 prefix 最大也接近 9 * 10^8单看似乎没问题但 prefix[i] - prefix[j] 的差值可能超过 int 范围吗不会因为差值就是子数组和最大不超过 9 * 10^8。不过在极端用例组合下最好直接用 long 类型避免在本地测试时踩到边界。我实际遇到过的情况是在面试白板上手写代码时用了 int被面试官追问“如果数值范围再大十倍呢”虽然题面不变但至少要让面试官知道你清楚有溢出的风险。5.4 面试时如何一步步引导思路如果面试遇到这题我个人推荐的表达顺序是先承认这就是“最大子数组和”的环形版本点出普通 Kadane 只覆盖了不跨环的情况。然后主动说“跨环的情况可以等价为总和减去中间最小段”这句话是整个题眼。接着把两种情况分别用 Kadane 求出来最后谨慎地处理全负数边界。整个过程最多 10 分钟讲完代码 15 分钟写完。我在实际面试中还被追问过“为什么这两种情况就覆盖了所有可能”这时候可以画一个环形图指着图说任意一个环形子数组要么不跨过起始点要么跨过起始点跨过起始点的那部分在补集意义上就是中间一段连续元素。这是分类讨论的完备性不是拍脑袋。最后分享一个小经验这题我建议直接做成模板记下来不仅仅是记代码而是记“环形数组最大/最小段”的通用套路。之后遇到“环形子数组最小和”“环形子数组和为 K”之类的变体题解题路径基本都逃不出这两种思路的组合。刷题这件事举一反三的收益远大于刷数量。 LeetCode 918环形子数组最大和：Kadane与单调队列两种解法
1. 先搞懂环形子数组和普通子数组差在哪LeetCode 918 这道题本质上是在 53 题“最大子数组和”的基础上把数组从一条直线首尾相连变成了一个环。很多人第一次做的时候第一反应是“这不就多了一种跨越边界的情况吗”然后直接套 Kadane 算法结果发现答案不对卡在 [5, -3, 5] 这种用例上——普通数组的最大子数组和是 5但环形数组能取到 [5, 5]一个在开头一个在结尾首尾相接答案应该是 10。这就是环形子数组和普通子数组最核心的区别子数组的起点和终点不再受数组边界的限制。换成人话说普通数组只能从某个位置开始、往后连续取环形数组可以从任意位置开始绕一圈回到起点之前的位置只要总长度不超过 n。这个“长度不超过 n”的约束也是后面两种解法里反复出现的重点因为如果允许取整个数组再绕一圈那就等于可以无限累加没有意义了。1.1 暴力枚举是怎么做的先看最直观的做法。枚举所有可能的子数组起点 i然后从 i 开始往后累加最多累加 n 个元素因为环形数组里连续子数组的长度不可能超过 n用取模的方式模拟绕圈。这样两重循环外层枚举起点内层枚举长度时间复杂度 O(n^2)。代码写出来倒是很简单def maxSubarraySumCircular(nums): n len(nums) ans float(-inf) for i in range(n): cur 0 for length in range(1, n 1): cur nums[(i length - 1) % n] ans max(ans, cur) return ans这个解法在 LeetCode 上直接超时因为 n 可以达到 3 * 10^4O(n^2) 是 9 亿次操作任何语言都扛不住。但它最大的价值在于帮我们建立了对题目的正确认知环形子数组本质上就是从某个点开始、顺时针连续取一段长度不超过 n。1.2 把环形问题拆成两种形态暴力解法虽然慢但给我们提供了一个重要的分类视角。任意一个环形子数组按照是否跨越了原数组的末尾边界可以分成两类第一类是不跨越边界的普通子数组比如 [1, -2, 3, -2] 里的 [3]它和 53 题完全一样直接在原数组上用 Kadane 算法求最大子数组和就行。第二类是跨越边界的环形子数组比如 [5, -3, 5] 里的 [5, 5]由末尾的 5 和开头的 5 拼成。这类子数组有一个非常优美的补集关系如果整个数组的总和是 total一个跨越边界的最大子数组等于 total 减去“在数组中间去掉的那一段连续子数组的和”。因为环形数组取一段剩下的就是另一段连续的部分取首尾相连的一段剩下的一定是中间连续的一段。于是核心问题就变成了求数组中连续子数组的最小和。这个转换是整个题目的灵魂解法二就是基于这个思想做的解法一则是换了一个角度用双倍数组把环形问题压平成线性问题。两条路最终都能到达终点但适用场景和坑位完全不同。2. 解法一双倍数组 前缀和 单调队列这个解法的思路非常工程化一句话概括把环形数组复制一份接在后面得到长度为 2n 的线性数组然后用一个固定最大长度 n 的滑动窗口在这个线性数组里找最大子数组和。2.1 为什么数组翻倍就能解决环形设想一下环形数组里的任意一个合法子数组如果把数组从某个位置切断并展平这个子数组可能因为跨越切口而断成两截。但如果把数组复制一份拼接起来任何一个长度不超过 n 的连续子数组一定能在这个 2n 长度的数组里找到完整的一段。比如 [5, -3, 5] 中的 [5, 5]在 [5, -3, 5, 5, -3, 5] 里就是第 3 到第 4 个元素连续且完整。翻倍之后问题就变成了在一个长度为 2n 的数组里找到长度不超过 n 的连续子数组的最大和。注意这里有个“长度不超过 n”的限制不能直接在整个 2n 数组上跑 Kadane因为那样可能取到长度超过 n 的子数组比如把所有 6 个元素都取了那就相当于绕了不止一圈。2.2 单调队列到底在维护什么要在滑动窗口内快速求最大子数组和经典的“前缀和 单调队列”组合是首选。前缀和数组 prefix 的定义是 prefix[i] sum(arr[0..i-1])这样任意区间 [j, i-1] 的和就是 prefix[i] - prefix[j]。那么固定右端点 i以 i-1 结尾的最大子数组和就是 prefix[i] - min(prefix[j])其中 j 必须落在窗口内也就是 i - j n。换句话说我们每次要拿到窗口内前缀和最小的那个位置。单调队列在这里扮演的角色就是“滑动窗口内最小值”的维护器。队列里存的是下标从队首到队尾对应的 prefix 值严格递增这样队首永远是当前窗口内前缀和最小的位置。每次 i 向右移动时先移除所有使得窗口长度超过 n 的过期下标i - q[0] n 就弹出队首然后用当前前缀和 prefix[i] 更新答案再把 prefix[i] 从队尾插入并维持单调性。有人可能会问为什么不能直接在窗口内跑 Kadane因为那样每次窗口滑动都要重新计算复杂度退化。而前缀和配合单调队列每次操作均摊 O(1)整体 O(n)。2.3 完整代码与复杂度分析from collections import deque def maxSubarraySumCircular(nums): n len(nums) arr nums nums # 双倍数组 prefix [0] * (2 * n 1) for i in range(2 * n): prefix[i 1] prefix[i] arr[i] q deque([0]) # 存下标对应前缀和单调递增 ans float(-inf) for i in range(1, 2 * n 1): # 保证窗口长度不超过 n窗口起点是 q[0]终点是 i-1 while q and i - q[0] n: q.popleft() # 以 i-1 结尾的最大子数组和 ans max(ans, prefix[i] - prefix[q[0]]) # 维持单调队列单调性当前前缀和下标入队 while q and prefix[q[-1]] prefix[i]: q.pop() q.append(i) return ans时间复杂度 O(n)双倍数组只是常数 2空间复杂度 O(n)主要花在 prefix 数组上。实测这套代码在 LeetCode 上运行时间稳定在 200ms 以内Python3内存占用约 17MB。这个解法的优点是思路直白不需要分类讨论只要理解了“滑动窗口 最小前缀和”就能写出来。缺点是代码稍微长一点而且单独写一个单调队列对不熟悉的人不太友好。3. 解法二Kadane 变体更推荐面试写解法二是基于补集思想做的代码更短也更接近面试官想听到的推理过程。核心公式是答案 max(最大非环子数组和, 总和 - 最小非环子数组和)其中“最大非环子数组和”就是标准 Kadane 算法跑一遍的结果“最小非环子数组和”则是把 Kadane 的 max 换成 min求整个数组里和最小的连续子数组。3.1 最大非环子数组和标准 KadaneKadane 算法的核心是动态规划。定义 dp[i] 为以 nums[i] 结尾的最大子数组和则转移方程为dp[i] max(nums[i], dp[i-1] nums[i])意思是要么从 nums[i] 重新开始一段要么把 nums[i] 接到之前的最优段后面。最终结果 dp 数组里的最大值就是答案。代码习惯上用一个变量滚动更新不占用额外数组。max_cur max_best nums[0] for i in range(1, n): max_cur max(nums[i], max_cur nums[i]) max_best max(max_best, max_cur)3.2 最小子数组和对称写法最小子数组和完全同理把 max 换成 min 即可。dp_min[i] min(nums[i], dp_min[i-1] nums[i])表示以 nums[i] 结尾的最小子数组和。min_cur min_best nums[0] for i in range(1, n): min_cur min(nums[i], min_cur nums[i]) min_best min(min_best, min_cur)一个很自然的疑问是为什么“总和 - 最小子数组和”一定对应一个合法的环形子数组我个人的理解方式是把环形子数组想成在环上取了一段那剩下没取的部分一定是环上另一段连续部分而“总和 - 最小段”就等价于“最大可取得段”。比如 [5, -3, 5]总和是 7最小子段是 [-3]两者相减等于 10正好是我们要的 [5, 5]。这个转化不需要证明画个环形图一眼就懂。3.3 全负数边界最大的坑如果数组里全是负数比如 [-2, -3, -1]最大非环子数组和是 -1最小非环子数组和是整个数组 -6总和是 -6于是“总和 - 最小子数组和”等于 0这明显是错的——环形子数组不能为空不能返回 0。为什么会出现这个错误因为“总和 - 最小子数组和”在最小子数组等于整个数组时计算结果是 0对应空集。只有全负数时整个数组才是最小子数组所以这个分支会算出空集。解决办法是特判如果 max_best 0说明所有元素都是负数直接返回 max_best此时它等于最大单个元素。因为任何长度大于 1 的连续子数组只会更小所以答案就是最大的那个负数。if max_best 0: return max_best这个判断必须放在最后不能写成“if total min_best”这种形式因为当数组里恰好有 0 时total min_best 也可能成立但此时答案可能不是负数。比如 [0, -1, -2]总和是 -3min_best 是 -3total - min_best 0但实际答案应该是 0取子数组 [0]所以单靠 total min_best 判断不够准确用 max_best 0 判断最稳妥。3.4 完整代码与复杂度分析def maxSubarraySumCircular(nums): n len(nums) total sum(nums) max_cur max_best nums[0] min_cur min_best nums[0] for i in range(1, n): max_cur max(nums[i], max_cur nums[i]) max_best max(max_best, max_cur) min_cur min(nums[i], min_cur nums[i]) min_best min(min_best, min_cur) # 全负数任何跨环子数组不可能比单个最大元素更大 if max_best 0: return max_best return max(max_best, total - min_best)时间复杂度 O(n)空间复杂度 O(1)只用了几个变量。代码量是两种解法里最少的而且不需要额外的数据结构。4. 两种解法对比与选型建议很多人关心这两种解法到底该选哪种我直接把对比列出来维度解法一双倍数组 前缀和 单调队列解法二Kadane 变体时间复杂度O(n)O(n)空间复杂度O(n)O(1)代码量偏长需要额外处理双倍数组和队列很短一个循环搞定易错点窗口长度限制、队列过期判断全负数特判思考路径压平环形转化为线性滑窗补集思想分类讨论面试友好度中需要解释单调队列原理高推理过程很自然我的建议是如果是面试优先讲解法二。原因是它的推导过程非常清晰从“环形问题拆成不跨环和跨环两类”到“跨环等于总和减最小子数组”每一步都有明确的逻辑支撑面试官很容易跟得上。而且代码短写完不容易有问题全负数特判还能展示你的严谨性。解法一的适用场景是当你对单调队列很熟或者面试官明确要求不能用分类讨论、必须用统一的滑窗思路时它可以作为备选。实际上我在面试中被追问过“如果还要支持动态修改数组元素怎么办”这时候解法一的思路就更有扩展性因为前缀和结构容易改造成线段树或树状数组。如果是在 LeetCode 上刷题我建议两种都写一遍。解法二帮你记住核心逻辑解法一帮你复习单调队列。两个都动手写过之后下次遇到“环形数组 最大子数组”这类变体题基本上都能很快定位到正确解法。5. 刷题与面试中的常见坑5.1 四个必测的边界用例我在提交之前一定会跑这组用例命中率极高输入预期输出说明[1, -2, 3, -2]3常见混合正负[5, -3, 5]10跨环边界关键用例[-2, -3, -1]-1全负数特判[0, 1, 2]3含 0不需要跨环其中 [5, -3, 5] 是检验“是否真正处理了跨环情况”的试金石很多错误实现会返回 5。全负数用例则能检验你是否考虑到了空集的陷阱。5.2 为什么不能直接套普通滑窗有人想既然解法一用了双倍数组和滑动窗口那能不能直接维护一个长度为 n 的滑动窗口窗口内跑 Kadane理论上可以但每次窗口移动时重新计算窗口内最大子数组和是 O(n) 的整体变成 O(n^2)。这也是为什么需要前缀和 单调队列来把单次查询降到 O(1) 的原因。还有一个常见的误区直接在双倍数组上跑标准 Kadane不管长度限制。比如 [5, -3, 5] 的双倍数组是 [5, -3, 5, 5, -3, 5]标准 Kadane 会算出 17整个数组求和因为 [5, -3, 5, 5, -3, 5] 全加起来等于 17。但环形数组的合法子数组长度不能超过 3所以这个结果是错的。这也是为什么解法一里窗口长度限制是解题关键不是可选项。5.3 Java/C 里的整型溢出细节如果你用 Java 或 C 写解法二total 可能达到 3 * 10^9 级别n 最大 3 * 10^4每个元素最大 3 * 10^4总和最大 9 * 10^8还没到 int 上限 2.1 * 10^9但接近了。更危险的是 prefix 数组在解法一里2n 长度下的 prefix 最大也接近 9 * 10^8单看似乎没问题但 prefix[i] - prefix[j] 的差值可能超过 int 范围吗不会因为差值就是子数组和最大不超过 9 * 10^8。不过在极端用例组合下最好直接用 long 类型避免在本地测试时踩到边界。我实际遇到过的情况是在面试白板上手写代码时用了 int被面试官追问“如果数值范围再大十倍呢”虽然题面不变但至少要让面试官知道你清楚有溢出的风险。5.4 面试时如何一步步引导思路如果面试遇到这题我个人推荐的表达顺序是先承认这就是“最大子数组和”的环形版本点出普通 Kadane 只覆盖了不跨环的情况。然后主动说“跨环的情况可以等价为总和减去中间最小段”这句话是整个题眼。接着把两种情况分别用 Kadane 求出来最后谨慎地处理全负数边界。整个过程最多 10 分钟讲完代码 15 分钟写完。我在实际面试中还被追问过“为什么这两种情况就覆盖了所有可能”这时候可以画一个环形图指着图说任意一个环形子数组要么不跨过起始点要么跨过起始点跨过起始点的那部分在补集意义上就是中间一段连续元素。这是分类讨论的完备性不是拍脑袋。最后分享一个小经验这题我建议直接做成模板记下来不仅仅是记代码而是记“环形数组最大/最小段”的通用套路。之后遇到“环形子数组最小和”“环形子数组和为 K”之类的变体题解题路径基本都逃不出这两种思路的组合。刷题这件事举一反三的收益远大于刷数量。