环形子数组的最大和 图解题解
这道题到底在问什么
- 输入
- nums=[1,-2,3,-2]
- 输出
- 3 （不绕环，取 [3]）
- 输入
- nums=[5,-3,5]
- 输出
- 10 （绕环，取末尾 5 接开头 5）
- 输入
- nums=[-3,-2,-3]
- 输出
- -2 （全负，只能取最大的单个）
最优解：一步一步想明白
- 3一句话:同时跑两个 Kadane(一个求最大段、一个求最小段),答案 = max(bestMax, total - bestMin),全负时只取 bestMax。
- 4先把整个数组的和 total=2 一次性求出来(后面是个常量);再让两个 Kadane 都从第 0 个元素 5 起步:绿色是「正在生长的最大段」,红色是「正在生长的最小段」,此刻都只含 5。
- 5看第 1 个 -2(紫)。先问绿色「最大段」:把 -2 接到前段(5)得 3,还是 -2 单飞更大?
- 6接上去更大,绿色段延伸,maxEnd=3。没超过 bestMax=5,保持。
- 7同一个 -2,换红色「最小段」视角:接上前段(5)得 3,还是 -2 单飞更小?
- 8单飞更小,红色段从 -2 重新开始,minEnd=-2。刷新 bestMin=-2。
- 9看第 2 个 3(紫)。先问绿色「最大段」:把 3 接到前段(3)得 6,还是 3 单飞更大?
- 10接上去更大,绿色段延伸,maxEnd=6。超过旧 bestMax,刷新 bestMax=6。
- 11同一个 3,换红色「最小段」视角:接上前段(-2)得 1,还是 3 单飞更小?
- 12接上去更小,红色段延伸,minEnd=1。没小过 bestMin=-2,保持。
- 13看第 3 个 -8(紫)。先问绿色「最大段」:把 -8 接到前段(6)得 -2,还是 -8 单飞更大?
- 14接上去更大,绿色段延伸,maxEnd=-2。没超过 bestMax=6,保持。
- 15同一个 -8,换红色「最小段」视角:接上前段(1)得 -7,还是 -8 单飞更小?
- 16单飞更小,红色段从 -8 重新开始,minEnd=-8。刷新 bestMin=-8。
- 17看第 4 个 4(紫)。先问绿色「最大段」:把 4 接到前段(-2)得 2,还是 4 单飞更大?
- 18单飞更大,绿色段从 4 重新开始,maxEnd=4。bestMax 仍是 6。
- 19同一个 4,换红色「最小段」视角:接上前段(-8)得 -4,还是 4 单飞更小?
- 20接上去更小,红色段延伸,minEnd=-4。没小过 bestMin=-8,保持。
- 21先看不绕环:最大子数组是绿色这段(5+-2+3 = 6)。这是候选 A。
- 22再看绕环:要绕环,就等于「挖掉中间一段、留两头」。挖掉的越小越好 → 挖掉红色这段最小子数组(和 = -8)。
- 23挖掉红段后,剩下两头(绿色)绕环接成一段:2 - (-8) = 10。这是候选 B,正是末尾绕回开头的那段。
- 24两个候选取大:B 更大,绕环胜出,答案 = 10(高亮即最终选中的那段)。
⚠️ 容易写错的地方
✗ 错：全负时返回 total - bestMin
✓ 对：bestMax < 0 时直接返回 bestMax
全负数组绕环会挖掉整个数组、剩空段(和为 0),但题目要求非空
✗ 错：只跑最大 Kadane
✓ 对：必须同时跑最小 Kadane
绕环的最大和 = total - 最小子数组和,缺了最小段就漏了绕环情况
✗ 错：把环展开成 2n 长度再做
✓ 对：双 Kadane 即可
展开 2n 还要限制窗口长度 ≤ n,更复杂;双 Kadane 一遍 O(n) 更优
完整代码（Python / C++ / Java）
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);
}
}复杂度
时间
O(n)
先求一遍 total,再一趟扫描同时跑两个 Kadane,都是线性
空间
O(1)
只用 maxEnd/minEnd/bestMax/bestMin/total 几个标量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 环形子数组的最大和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和普通的「最大子数组和」(LC53)有什么关系?+
LC53 只有不绕环一种情况,Kadane 一遍即可。LC918 多了绕环情况,做法是再跑一个「最小子数组」Kadane,用 total - bestMin 算出绕环的最大和,与 bestMax 取大,并处理全负陷阱。本质是 LC53 的环形扩展。
除了双 Kadane,还有别的思路吗?+
可以把数组复制成 2n 长度,用前缀和加单调队列,在窗口长度 ≤ n 的约束下求最大区间和,也是 O(n)。但实现更繁琐,双 Kadane 更简洁,是面试首选。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 环形子数组的最大和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。