90.环形子数组的最大和
题目
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
- 输入：nums = [1,-2,3,-2]
- 输出：3
- 解释：从子数组 [3] 得到最大和 3
示例 2：
- 输入：nums = [5,-3,5]
- 输出：10
- 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
- 输入：nums = [3,-2,2,-3]
- 输出：3
- 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示：
- n == nums.length
- 1 <= n <= 3 * 104
- -3 * 104 <= nums[i] <= 3 * 104
思路
"环形"的意思是：下标 n-1 的下一个是下标 0，所以子数组可以跨过末尾绕回开头。
nums = [5, -3, 5]
不绕圈：5 + (-3) + 5 = 7 绕圈： 末尾的 5 → 绕回 → 开头的 5 = 10 ✅ 答案
但有一条硬约束：每个元素最多只能用一次，也就是子数组长度不能超过 n。不能绕两圈把 5 数两遍。
面对环形，硬去枚举"从哪开始、绕多远"会很乱。正确的第一步是分类：
最优子数组要么绕圈，要么不绕圈，没有第三种可能。
情况 A：不跨越边界 [ . . ■ ■ ■ . . ] 就是普通数组的最大子数组和 → 53 题的 Kadane └─────┘
情况 B：跨越边界 [ ■ ■ . . . ■ ■ ] 由一段前缀 + 一段后缀组成 └─┘ └─┘
情况 A 直接调用上一题的 Kadane 就完事了。问题全在情况 B。
情况 B 的关键洞察：看它的"补集"
前缀 + 后缀这个形状不好直接算。但请注意它剩下的那部分：
下标: 0 1 2 3 4 5 [ ■ ■ □ □ ■ ■ ] └─前缀─┘ └─后缀─┘ └─中间─┘
被挖掉的"中间那段"，恰好是一个普通的、连续的、不绕圈的子数组。
于是：
绕圈子数组的和 = 数组总和 − 中间那段的和
想让左边最大，就要让"中间那段的和"最小。而"求最小连续子数组和"——就是把 Kadane 里的 max 全换成 min，一模一样的算法。
于是整道题的解法浮现了：
▎ 一次遍历，同时算出三样东西：总和 total、最大子数组和 bestMax、最小子数组和 bestMin。 ▎ ▎ 答案 = max(bestMax, total - bestMin)
一个 O(n) 的循环解决，不需要真的去处理环形。
手动走一遍 [5, -3, 5]
┌─────┬─────┬────────────────┬─────────┬─────────────────┬─────────┬───────┐ │ i │ x │ curMax │ bestMax │ curMin │ bestMin │ total │ ├─────┼─────┼────────────────┼─────────┼─────────────────┼─────────┼───────┤ │ 0 │ 5 │ 5 │ 5 │ 5 │ 5 │ 5 │ ├─────┼─────┼────────────────┼─────────┼─────────────────┼─────────┼───────┤ │ 1 │ -3 │ max(-3, 2) = 2 │ 5 │ min(-3, 2) = -3 │ -3 │ 2 │ ├─────┼─────┼────────────────┼─────────┼─────────────────┼─────────┼───────┤ │ 2 │ 5 │ max(5, 7) = 7 │ 7 │ min(5, 2) = 2 │ -3 │ 7 │ └─────┴─────┴────────────────┴─────────┴─────────────────┴─────────┴───────┘
- 情况 A：bestMax = 7
- 情况 B：total - bestMin = 7 - (-3) = 10
答案 max(7, 10) = 10 ✅
bestMin = -3 对应的是中间那个 -3，把它挖掉剩下的正是首尾两个 5 —— 和我们预期的绕圈答案完全对上。
四、必须特判的坑：全是负数
这个公式有一个漏洞。看 [-3, -2, -3]：
- total = -8
- bestMax = -2（只选那个最大的负数）
- bestMin = -8（整个数组就是最小子数组）
- total - bestMin = -8 - (-8) = 0
于是公式给出 max(-2, 0) = 0。但 0 是不合法的——它对应的是"把整个数组都挖掉"，剩下一个空子数组。而题目要求非空。正确答案是 -2。
问题的本质： 当 bestMin 恰好等于整个数组的和时，情况 B 的"中间段"吞掉了一切，前缀和后缀都空了。
修法（一行）：
if (bestMax < 0) return bestMax
为什么这一行就够？ 因为 bestMax < 0 等价于"数组里全是负数"（只要有一个元素 ≥ 0，bestMax 就至少是它，不可能为负）。而全负数时，最优答案就是那个最大的负数，也就是 bestMax。
反过来，只要有一个元素 ≥ 0，那么 bestMax ≥ 0，此时哪怕公式算出了那个虚假的 0，max(bestMax, 0) = bestMax 也不会被它污染。所以这个特判是严密的，不是打补丁。
class Solution {
/**
* 环形子数组的最大和
*
* 核心思想：答案只有两种形态 ——
* A) 不跨越边界 → 就是普通的最大子数组和（Kadane）
* B) 跨越边界（前缀 + 后缀）→ 它的补集"中间那段"是一个普通连续子数组，
* 所以此时和 = total - 最小子数组和
* 答案 = max(A, B)
*
* 时间复杂度 O(n)：一次遍历同时算出三个量
* 空间复杂度 O(1)：只用几个变量
*/
fun maxSubarraySumCircular(nums: IntArray): Int {
var total = 0 // 数组总和
// 一组跑最大（Kadane 原版）
var curMax = 0 // 以当前元素结尾的最大子数组和
var bestMax = Int.MIN_VALUE // 全局最大子数组和
// 一组跑最小（把 max 换成 min，完全对称）
var curMin = 0 // 以当前元素结尾的最小子数组和
var bestMin = Int.MAX_VALUE // 全局最小子数组和
for (x in nums) {
total += x
// 决策同 53 题：接着前面那段继续，还是从我这里重开一段
curMax = maxOf(x, curMax + x)
bestMax = maxOf(bestMax, curMax)
// 镜像逻辑：前面累积和是正数就是拖累，甩掉重开
curMin = minOf(x, curMin + x)
bestMin = minOf(bestMin, curMin)
}
// ⚠️ 必须特判：bestMax < 0 等价于"全是负数"。
// 此时 bestMin 就是 total，total - bestMin = 0 对应空子数组，非法。
// 全负数时答案就是那个最大的负数，即 bestMax。
if (bestMax < 0) return bestMax
// 情况 A 与情况 B 取较优
return maxOf(bestMax, total - bestMin)
}
}
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(1)
- 邮箱 ：charon.chui@gmail.com
- Good Luck!