环形数组的最大子数组和：Kadane 算法的巧妙扩展

题目与常规 Kadane 回顾

题目：给定一个「环形」整数数组 nums，要求返回一个非空连续子数组的最大和。leetcode

如果数组不是环而是直线，这就是经典的「最大子数组和」问题，可以直接用Kadane 算法解决：

• 维护当前前缀最优curMax：到当前位置为止、必须以当前元素结尾的最大和。
• 转移：curMax = max(nums[i], curMax + nums[i])。
• 同时更新全局答案maxSub = max(maxSub, curMax)。

这一套可以得到「不回环」情况下的最大子数组和。

环形数组的关键拆分思路

环形的麻烦在于子数组可以「跨尾到头」，例如[5, -3, 5]的最优子数组是[5, 5]，中间的-3被跳过。

关键观察：环形最大子数组只有两种形态：

1. 不回环：

   • 像普通数组那样，在中间某一段上，完全不跨越尾和头。
   • 对应答案就是经典 Kadane 的maxSub。

2. 回环：

   • 形态类似「尾巴一段 + 头部一段」，中间有一段连续区间被"挖掉不选"。
   • 把数组想象成一圈：
     • 选中的一整圈减去"中间没选的那一段" = 回环子数组。
   • 如果记数组总和为total，中间那段是一个「连续子数组」，它的和记为minSub，则
     • 回环子数组和 =total - minSub。

所以：

• 不回环答案：maxSub（普通最大子数组和）
• 回环答案：total - minSub（总和减去"最小子数组和"）

最终答案应该是两者的较大值：

ans = max ⁡ ( maxSub , total − minSub ) \text{ans} = \max(\text{maxSub},\, \text{total} - \text{minSub})ans=max(maxSub,total−minSub)

为什么要用「总和 - 最小子数组」？

用示例nums = [5, -3, 5]直观理解：

• 数组总和：
  t o t a l = 5 + ( − 3 ) + 5 = 7 total = 5 + (-3) + 5 = 7total=5+(−3)+5=7

• 所有连续子数组中，和最小的是[-3]，所以minSub = -3。

• 把[-3]这段挖掉，其余部分是[5]（尾部）加上[5]（头部），组成回环子数组[5, 5]。

• 用公式：
  t o t a l − m i n S u b = 7 − ( − 3 ) = 10 total - minSub = 7 - (-3) = 10total−minSub=7−(−3)=10
  正好就是[5, 5]的和。

这个思路的本质：

• 回环子数组 = 整个环 - 某一段连续区间。
• 想让留下来的和最大，就要让被挖掉那一段的和尽量小，于是变成「最小子数组和」问题。

最小子数组和同样可以用一个“反向 Kadane”求出来，只是把max换成min：

• curMin = min(nums[i], curMin + nums[i])
• minSub = min(minSub, curMin)。

全负数的坑：为什么这时只能用 maxSub？

看nums = [-3, -2, -3]这个例子：

1. Kadane 最大子数组和：

   • 最佳选择是[-2]，所以maxSub = -2。

2. 数组总和：
   t o t a l = − 3 + ( − 2 ) + ( − 3 ) = − 8 total = -3 + (-2) + (-3) = -8total=−3+(−2)+(−3)=−8

3. 最小子数组和：

   • 在全负数组上，求“最小子数组和”的 Kadane 会把整段都选上，得到minSub = -8，而且此时minSub == total。

4. 代入回环公式：
   t o t a l − m i n S u b = − 8 − ( − 8 ) = 0 total - minSub = -8 - (-8) = 0total−minSub=−8−(−8)=0

问题来了：

• 这个0表面上看比maxSub = -2大，但它代表的含义是：
  • 「把整段都当成中间被挖掉的最小子数组，剩下的部分为空」——即根本没选任何元素。
  • 但题目要求子数组必须非空，所以total - minSub在这种情况下其实是非法结果。

因此，对于「最小子数组就是整个数组」的情况（minSub == total），只能认为“没有合法的回环方案”，只能依赖不回环的maxSub。

这就是常见代码里的特判：

if (minSub == total) // 最小子数组等于整段 => 全负或等价情况 return maxSub; else return max(maxSub, total - minSub);

这样就避免了选「空子数组」的假结果。

一次遍历实现整体算法

整体算法可以在一次循环中完成：同时维护最大子数组、最小子数组和总和。

核心变量设计：

• curMax：到当前下标、必须以当前元素结尾的最大子数组和。
• maxSub：全局最大子数组和（不回环）。
• curMin：到当前下标、必须以当前元素结尾的最小子数组和。
• minSub：全局最小子数组和。
• total：数组总和。

每轮迭代：

1. curMax = max(nums[i], curMax + nums[i])；maxSub = max(maxSub, curMax)。
2. curMin = min(nums[i], curMin + nums[i])；minSub = min(minSub, curMin)。
3. total += nums[i]。

循环结束后：

• 如果minSub == total，说明最小子数组等于整段，只能返回maxSub。
• 否则返回max(maxSub, total - minSub)。

时间复杂度 O(n)、空间 O(1)，同时处理了：

• 只在中间的一段（不回环）；
• 从尾到头跨越的一段（回环）；
• 全负数等特殊情况。

思路要点小结

1. 不必在环上「拼成 2n 数组 + 枚举起点」，那样要么 O(n²)，要么需要复杂的长度约束，不适合这题。

2. 环形最大子数组拆成两种模式：不回环用 Kadane 求maxSub，回环用total - minSub。

3. 用「全负数时minSub == total」这个条件判断是否存在合法的回环方案；如果不存在，就只能选最大单个元素，也就是maxSub。

4. 整题的本质就是：

   • 在环上做 Kadane 的最佳方式，是同时维护「最大子数组」和「最小子数组」，并用「总和减最小」来间接表示回环情况。