题目描述
思路解析动画文字版
一句话:同时跑两个 Kadane(一个求最大段、一个求最小段),答案 = max(bestMax, total - bestMin),全负时只取 bestMax。
先把整个数组的和 total=2 一次性求出来(后面是个常量);再让两个 Kadane 都从第 0 个元素 5 起步:绿色是「正在生长的最大段」,红色是「正在生长的最小段」,此刻都只含 5。
看第 1 个 -2(紫)。先问绿色「最大段」:把 -2 接到前段(5)得 3,还是 -2 单飞更大?
接上去更大,绿色段延伸,maxEnd=3。没超过 bestMax=5,保持。
同一个 -2,换红色「最小段」视角:接上前段(5)得 3,还是 -2 单飞更小?
单飞更小,红色段从 -2 重新开始,minEnd=-2。刷新 bestMin=-2。
看第 2 个 3(紫)。先问绿色「最大段」:把 3 接到前段(3)得 6,还是 3 单飞更大?
接上去更大,绿色段延伸,maxEnd=6。超过旧 bestMax,刷新 bestMax=6。
同一个 3,换红色「最小段」视角:接上前段(-2)得 1,还是 3 单飞更小?
接上去更小,红色段延伸,minEnd=1。没小过 bestMin=-2,保持。
看第 3 个 -8(紫)。先问绿色「最大段」:把 -8 接到前段(6)得 -2,还是 -8 单飞更大?
接上去更大,绿色段延伸,maxEnd=-2。没超过 bestMax=6,保持。
同一个 -8,换红色「最小段」视角:接上前段(1)得 -7,还是 -8 单飞更小?
单飞更小,红色段从 -8 重新开始,minEnd=-8。刷新 bestMin=-8。
看第 4 个 4(紫)。先问绿色「最大段」:把 4 接到前段(-2)得 2,还是 4 单飞更大?
单飞更大,绿色段从 4 重新开始,maxEnd=4。bestMax 仍是 6。
同一个 4,换红色「最小段」视角:接上前段(-8)得 -4,还是 4 单飞更小?
接上去更小,红色段延伸,minEnd=-4。没小过 bestMin=-8,保持。
先看不绕环:最大子数组是绿色这段(5+-2+3 = 6)。这是候选 A。
再看绕环:要绕环,就等于「挖掉中间一段、留两头」。挖掉的越小越好 → 挖掉红色这段最小子数组(和 = -8)。
挖掉红段后,剩下两头(绿色)绕环接成一段:2 - (-8) = 10。这是候选 B,正是末尾绕回开头的那段。
两个候选取大:B 更大,绕环胜出,答案 = 10(高亮即最终选中的那段)。
边界先想清:单元素、全负(取最大单个)、全正(整段)。
两个高频追问:与 LC53 的关系,以及单调队列的替代解法。
参考代码
from typing import Listclass 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)复杂度
- 时间：O(n)，先求一遍 total,再一趟扫描同时跑两个 Kadane,都是线性
- 空间：O(1)，只用 maxEnd/minEnd/bestMax/bestMin/total 几个标量
易错点
面试追问把动画讲成自己的话
追问和普通的「最大子数组和」(LC53)有什么关系?
追问除了双 Kadane,还有别的思路吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
将字符串翻转到单调递增
LeetCode 926 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题