环形子数组的最大和 图解题解

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

给一个整数数组 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。

Python

from typing import List
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        total = sum(nums)
        max_end = min_end = nums[0]
        best_max = best_min = nums[0]
        for i in range(1, len(nums)):
            x = nums[i]
            max_end = max(x, max_end + x)
            best_max = max(best_max, max_end)
            min_end = min(x, min_end + x)
            best_min = min(best_min, min_end)
        return best_max if best_max < 0 else max(best_max, total - best_min)

C++

#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int maxEnd = nums[0], minEnd = nums[0], bestMax = nums[0], bestMin = nums[0];
        for (int i = 1; i < (int)nums.size(); ++i) {
            int x = nums[i];
            maxEnd = max(x, maxEnd + x); bestMax = max(bestMax, maxEnd);
            minEnd = min(x, minEnd + x); bestMin = min(bestMin, minEnd);
        }
        return bestMax < 0 ? bestMax : max(bestMax, total - bestMin);
    }
};

Java

import java.util.*;
class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        int maxEnd = nums[0], minEnd = nums[0], bestMax = nums[0], bestMin = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            maxEnd = Math.max(x, maxEnd + x); bestMax = Math.max(bestMax, maxEnd);
            minEnd = Math.min(x, minEnd + x); bestMin = Math.min(bestMin, minEnd);
        }
        return bestMax < 0 ? bestMax : Math.max(bestMax, total - bestMin);
    }
}