环形子数组的最大和
题目描述：
给定一个长度为 n 的环形整数数组（即首尾相连），请你找出其中元素总和最大的非空子数组，并返回这个最大和。注意：子数组要求在原数组中连续（环形条件下允许跨越数组末尾和开头）。
示例：
输入：[3, -2, 2, -3]
输出：3
解释：最大和子数组为 [3]，总和为 3。注意环形条件下跨越头尾的子数组 [3, -2, 2] 总和也是 3，但最大和仍为 3。
第一步：理解环形带来的特殊情况
环形数组的最大子数组和有两种可能情况：
- 最大子数组不跨越环形边界：此时问题退化为普通数组的“最大子数组和”，可以用 Kadane 算法求解。
- 最大子数组跨越环形边界：跨越边界意味着子数组由数组尾部的一段和数组开头的一段组成，中间跳过了数组中间一部分。
- 思考：整个数组的总和是固定的。如果最大子数组跨越边界，相当于从原数组中挖掉中间一段（不包含在子数组中），而中间这一段其实就是原数组中总和最小的一段连续子数组。
- 结论：最大子数组和 = 数组总和 - 最小子数组和。
但要注意一种特殊情况：如果整个数组全是负数，那么最大子数组和就是数组中的最大单个元素（而不是数组总和 - 最小子数组和，因为此时最小子数组和就是整个数组，相减结果为 0，但这并不对应一个子数组）。
第二步：设计算法思路
我们可以用两个 Kadane 算法分别求解：
maxSum：普通最大子数组和（不跨越边界的情况）。minSum：普通最小子数组和（用于计算跨越边界的情况）。total：数组所有元素总和。
那么环形最大子数组和 = max( maxSum, total - minSum )，除非 minSum == total（即全负数的情况），此时直接返回 maxSum。
但全负数情况的判断可以简化：
如果 total == minSum，说明所有元素都是负数（因为最小子数组和等于总和，意味着整个数组就是最小子数组，此时所有元素非正，且最大子数组和是负数）。此时直接返回 maxSum 即可。
但注意：如果数组中有正有负，minSum 可能为负数，total - minSum 可能比 maxSum 大。
第三步：状态转移方程
设：
dpMax[i]表示以第 i 个元素结尾的最大子数组和。dpMin[i]表示以第 i 个元素结尾的最小子数组和。
递推：
dpMax[i] = max(nums[i], dpMax[i-1] + nums[i])dpMin[i] = min(nums[i], dpMin[i-1] + nums[i])
然后：
maxSum = max(dpMax[0..n-1])minSum = min(dpMin[0..n-1])
如果 maxSum < 0（等价于全数组负数），那么环形最大子数组和 = maxSum。
否则，环形最大子数组和 = max( maxSum, total - minSum )。
第四步：举例推演
以 nums = [3, -2, 2, -3] 为例：
初始化：
dpMax[0] = 3, dpMin[0] = 3, total = 3
i=1:
dpMax[1] = max(-2, 3 + (-2)) = 1
dpMin[1] = min(-2, 3 + (-2)) = 1? 等等，这里要小心：
正确计算 dpMin[1] = min(-2, 3 + (-2)) = min(-2, 1) = -2
total = 3 + (-2) = 1
i=2:
dpMax[2] = max(2, 1 + 2) = 3
dpMin[2] = min(2, -2 + 2) = 0
total = 1 + 2 = 3
i=3:
dpMax[3] = max(-3, 3 + (-3)) = 0
dpMin[3] = min(-3, 0 + (-3)) = -3
total = 3 + (-3) = 0
得到：
maxSum = max(3, 1, 3, 0) = 3
minSum = min(3, -2, 0, -3) = -3
total = 0
total - minSum = 0 - (-3) = 3
max( maxSum, total - minSum ) = max(3, 3) = 3
结果 3。
第五步：边界处理
如果数组中全是负数，比如 [-3, -2, -1]：
dpMax 序列: -3, -2, -1 → maxSum = -1
dpMin 序列: -3, -5, -6 → minSum = -6
total = -6
total - minSum = -6 - (-6) = 0
但此时不能取 0，因为子数组不能为空，应该取 maxSum = -1。
判断方法：如果 maxSum < 0，则返回 maxSum。
第六步：代码框架（Python）
def maxSubarraySumCircular(nums):
total = 0
maxSum = curMax = float('-inf')
minSum = curMin = float('inf')
for num in nums:
total += num
# 普通最大子数组和
curMax = max(num, curMax + num)
maxSum = max(maxSum, curMax)
# 普通最小子数组和
curMin = min(num, curMin + num)
minSum = min(minSum, curMin)
if maxSum < 0:
return maxSum
else:
return max(maxSum, total - minSum)
复杂度：O(n) 时间，O(1) 空间。
第七步：思考拓展
本题是 Kadane 算法在环形数组上的巧妙应用，核心是理解环形最大子数组要么是普通最大子数组，要么是总和减去普通最小于数组。
这个思路还可以推广到环形数组的“最小子数组和”问题，只需将上述逻辑反过来即可。