环形子数组的最大和

环形子数组的最大和在找什么

给一个整数数组 nums，首尾相连成环，最后一个后面接回第一个。要在环上找一段连续、非空的子数组让和最大，可从末尾绕过去接开头，每个下标最多用一次。比如 nums=[1,-2,3,-2] 不绕环取 [3] 得 3；nums=[5,-3,5] 则末尾 5 绕回接开头 5、跨过 -3，和为 10。

为什么不能把环剪断暴力枚举

把环剪断枚举所有连续段求和要 O(n²) 段，一大就吃不消。也有人复制成 2n 长再跑普通最大子数组，但得限制选段长度不超过 n，否则同一下标算两次，还要配前缀和加单调队列，繁。突破口是：环上最优段只有两种长相，分开处理一趟扫描就够。

绕环的最大，等于总和减去最小子数组

把答案分成互斥两类。第一类不绕环，就是普通连续子数组，正是最大子数组和问题（LeetCode 53）：一个 Kadane 一趟扫描就能求出，每步只决定把当前元素接前段后面、还是自己另起一段，记为 bestMax。

第二类绕环，选「末尾一截 + 开头一截」，中间空一段没选。total 固定，绕环选中的和 = total 减中间那段；想让它最大，就得让挖掉那段最小。所以绕环最大和 = total 减最小子数组和，同样用 Kadane 求，只把每步 max 换成 min，记为 bestMin。

为什么两个 Kadane 一趟就能同时算完

两个 Kadane 各维护 max_end、min_end（以当前元素结尾那段的最大、最小和）和 bestMax、bestMin（至今全局最优）。它们互不干扰，一个循环扫一遍全更新。答案取 bestMax 与 total - bestMin 里更大的：前者管不绕环，后者管绕环，取大即全局最优。

拿 [5,-3,5] 亲手算一遍

total = 5 + (-3) + 5 = 7，四个量起点都设成 nums[0]=5。到 -3：最大段接前面 5 得 2 比单飞大，max_end=2、bestMax 仍 5；最小段 -3 单飞更小，min_end=-3、bestMin=-3。到第二个 5：最大段接前面 2 得 7，max_end=7、bestMax=7；最小段接上得 2 更小，min_end=2、bestMin 仍 -3。收尾 bestMax=7、bestMin=-3，答案 max(7, 7-(-3)) = 10。total 减最小段 -3，正是挖掉中间 -3、留两头两个 5 相接的和。

复杂度多少，全负数组这个坑

求 total 一趟、双 Kadane 一趟都是线性，时间 O(n)；全程只用几个标量滚动，空间 O(1)。

最阴的是全负数组 nums=[-3,-2,-3]：total=-8，最小子数组是整个数组，bestMin=-8。照搬 total - bestMin = 0，等于把整个数组挖掉、剩和为 0 的空段，可题目要求非空，0 取不到。所以先看 bestMax：它 < 0 说明全负，绕环的 0 不合法，返回 bestMax（这里 -2）。另一坑是只跑最大 Kadane，绕环整类全丢，[5,-3,5] 会误答成 7。