环形数组的最大子段和问题
一、问题描述
给定一个长度为 \(n\) 的环形整数数组 \(nums\)（即数组的结尾与开头相连）。
要求：找出该环形数组中连续的一段子数组（长度至少为 1），使得这段子数组的元素之和最大。
返回这个最大的和。
示例
输入：nums = [5, -3, 5]
输出：10
解释：从索引 0 取到索引 2，子数组 [5, -3, 5] 是环形的连续段（即跨越末尾和开头），和为 5 + (-3) + 5 = 7，但最大的子数组是 [5, 5]（索引 0 和索引 2），和为 10。
二、思路分析
1. 环形带来的特殊情形
对于普通线性数组，最大子段和可以用 Kadane 算法 在 \(O(n)\) 时间内求出。
但在环形数组中，最大子段可能有两种情况：
- 不跨越环形边界：即最大子段位于数组中间，此时就是普通的最大子段和。
- 跨越环形边界：即子段由数组末尾的一部分和开头的一部分组成。
- 如果跨越边界，那么中间必然有一段被排除在外。
- 最大跨越边界的子段和 = 数组总和 - 中间被排除的那一段的和。
- 被排除的那一段是数组中间的连续段，并且它的和应该尽可能小。
因此，跨越环形边界的最大子段和 = 数组总和 - 最小子段和（注意：当最小子段和就是整个数组时，不能全排除，需要特殊处理）。
2. 问题转化
设：
- \(maxSum\) = 普通（不跨越边界）的最大子段和
- \(minSum\) = 普通的最小子段和
- \(total\) = 数组所有元素之和
则环形数组的最大子段和为：
\[\max(maxSum, \ total - minSum) \]
但有一个陷阱：如果最小子段和就是整个数组（即所有元素都是负数），那么 \(total - minSum = 0\)，这时我们不能取这个 0，因为必须至少选一个元素，而此时最大子段和就是数组中最大的那个负数（即 \(maxSum\)）。
实际上，当 \(maxSum < 0\) 时，说明全为负数，直接返回 \(maxSum\) 即可。否则，比较 \(maxSum\) 和 \(total - minSum\)。
3. Kadane 算法求最大和最小子段和
Kadane 算法：
- 以 \(dp[i]\) 表示以 \(i\) 结尾的最大子段和，则
\[ dp[i] = \max(nums[i], \ dp[i-1] + nums[i]) \]
遍历一次可得 \(maxSum\)。
- 同样，以 \(dpMin[i]\) 表示以 \(i\) 结尾的最小子段和，则
\[ dpMin[i] = \min(nums[i], \ dpMin[i-1] + nums[i]) \]
遍历一次可得 \(minSum\)。
三、详细推导
设初始：
\[maxEnding = nums[0], \quad maxSum = nums[0] \]
\[minEnding = nums[0], \quad minSum = nums[0] \]
\[total = nums[0] \]
从 \(i = 1\) 到 \(n-1\) 遍历：
- 更新 \(total\)：
\[ total += nums[i] \]
- 更新以 \(i\) 结尾的最大子段和：
\[ maxEnding = \max(nums[i], \ maxEnding + nums[i]) \]
\[ maxSum = \max(maxSum, \ maxEnding) \]
- 更新以 \(i\) 结尾的最小子段和：
\[ minEnding = \min(nums[i], \ minEnding + nums[i]) \]
\[ minSum = \min(minSum, \ minEnding) \]
遍历完后，得到 \(maxSum, minSum, total\)。
特殊情况处理：
如果 \(maxSum < 0\)（即所有数都是负数），则直接返回 \(maxSum\)。
否则，答案为：
\[\max(maxSum, \ total - minSum) \]
四、举例说明
例1：nums = [5, -3, 5]
遍历过程：
- i=0: total=5, maxEnding=5, maxSum=5, minEnding=5, minSum=5
- i=1: total=2, maxEnding=max(-3, 5+(-3)=2)=-3 → 2, maxSum=5, minEnding=min(-3,5+(-3)=2)=-3, minSum=-3
- i=2: total=7, maxEnding=max(5, 2+5=7)=7, maxSum=7, minEnding=min(5, -3+5=2)=2, minSum=-3
结束：
maxSum=7, minSum=-3, total=7
因为 maxSum>0，比较 maxSum 和 total-minSum=7-(-3)=10，取 10。
例2：nums = [-2, -3, -1]
遍历过程均为负数，最后 maxSum = -1（最大单个元素），minSum = -6，total = -6。
maxSum<0，直接返回 -1。
五、代码实现（伪代码）
function maxSubarraySumCircular(nums):
n = nums.length
total = nums[0]
maxEnding = nums[0], maxSum = nums[0]
minEnding = nums[0], minSum = nums[0]
for i from 1 to n-1:
total += nums[i]
maxEnding = max(nums[i], maxEnding + nums[i])
maxSum = max(maxSum, maxEnding)
minEnding = min(nums[i], minEnding + nums[i])
minSum = min(minSum, minEnding)
if maxSum < 0:
return maxSum
else:
return max(maxSum, total - minSum)
时间复杂度：\(O(n)\)
空间复杂度：\(O(1)\)
六、总结
这个问题巧妙利用了环形数组的特性：
- 不跨越边界 → 普通最大子段和
- 跨越边界 → 总和减去中间的最小子段和
- 特殊处理全负数情况
通过一次遍历同时计算最大和最小连续子段和，即可得到环形最大子段和。