环形数组的最大子数组和：Kadane 算法的巧妙扩展-平芜编程栈

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

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

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

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

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

所以：

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

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：

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

Kadane 最大子数组和：
- 最佳选择是[-2]，所以maxSub = -2。
数组总和：
t o t a l = − 3 + ( − 2 ) + ( − 3 ) = − 8 total = -3 + (-2) + (-3) = -8total=−3+(−2)+(−3)=−8
最小子数组和：
- 在全负数组上，求“最小子数组和”的 Kadane 会把整段都选上，得到minSub = -8，而且此时minSub == total。
代入回环公式：
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);

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

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

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

不必在环上「拼成 2n 数组 + 枚举起点」，那样要么 O(n²)，要么需要复杂的长度约束，不适合这题。
环形最大子数组拆成两种模式：不回环用 Kadane 求maxSub，回环用total - minSub。
用「全负数时minSub == total」这个条件判断是否存在合法的回环方案；如果不存在，就只能选最大单个元素，也就是maxSub。
整题的本质就是：
- 在环上做 Kadane 的最佳方式，是同时维护「最大子数组」和「最小子数组」，并用「总和减最小」来间接表示回环情况。