【LC 53】最大子数组和：Kadane 只有一句话 —— 带上前面那段，是赚了还是亏了
适用读者：背过 Kadane 但没想明白"为什么 cur < 0 就敢扔掉前面整段"的人；以及想知道分治解法到底在干什么的人
技术栈：Python 为主，附 Java 版
难度：Medium —— 代码五行，但它的 DP 定义、"负资产"论证和分治的四元组，各值一场面试
收获：Kadane 的 DP 本质与"负资产"论证、返回子数组本身的写法、分治解法的四元组合并（线段树的基础）、LC 918 环形版如何把同一个算法反着用
题目
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
输入：nums = [1]
输出：1
输入：nums = [5,4,-1,7,8]
输出：23
这题看起来人畜无害 —— 谁不会写两层循环枚举所有子数组呢？但它是腾讯的 TOP 4、阿里数据岗的必刷题，因为它在短短五行代码里装了三样东西：
一、核心洞察：整道题只有一句话
从左到右扫，只维护一个量：
cur = 以当前位置结尾的最大子数组和。
扫到
x 时，以
x 结尾的最大子数组和只有两种可能：
① 接在前面那段后面 → cur + x
② 从 x 自己重新开始 → x
取更大的那个：
这是一个标准的
动态规划定义：状态是"以
i 结尾的最大子数组和"，转移只有上面两种 —— 从
O(n²) 种候选坍缩到每个位置 2 种。
这一句从头到尾只在问一件事：带上前面那段，是赚了还是亏了？
把
max 拆开看：
- 若
cur + x >= x，即 cur >= 0 —— 前面那段不亏，带着走；
- 若
cur + x < x，即 cur < 0 —— 前面那段是负资产，扔掉，从 x 重新开始。
所以"要不要重置"的判据
不在 x 身上，而在 cur 身上：
x 自己没有任何选择权，它只能决定"接上之后我值多少"；真正有选择权的是前面那段 —— 它是正的就带上，是负的就扔掉。
全程再用一个
best 记录
cur 的历史最大值。
best 的含义是"
所有位置里，以某个位置结尾的最大子数组和的最大值" —— 因为任何一个子数组都必然以某个位置结尾，所以扫完
best 就是全局答案。
二、完整代码（顺带把子数组本身也返回了）
def maxSubArray(nums):
cur = best = nums[0] # 子数组至少含一个元素，从 nums[0] 起步
start = bestStart = bestEnd = 0
for i in range(1, len(nums)):
if cur < 0: # 前面那段是负资产 → 扔掉，从 i 重新开始
cur = nums[i]
start = i
else: # 前面那段是正的 → 带上
cur = cur + nums[i]
if cur > best: # 刷新全局最优时，把当前区间记下来
best = cur
bestStart, bestEnd = start, i
return best, nums[bestStart:bestEnd + 1]
：题解里常见的
cur = max(x, cur + x) 和这里的
if cur < 0 是同一件事的两种说法：
cur = max(x, cur + x) # 值视角：两个候选取大
if cur < 0: 从 x 重新开始 # 位置视角：判据是"前面那段是不是负的"
写返回值用第一句最短；但
"返回子数组本身"必须用第二句 —— 因为位置信息只存在于第二句里。这也是为什么本文的动画用
if cur < 0 的写法：它能让"扔掉哪段、从哪重起"变成看得见的动作。
初始化还有一个容易错的点：
cur 和 best 都从 nums[0] 起步，而不是 0。子数组至少含一个元素 —— 全负数组的答案是那个最大的负数，从 0 起步会把它错答成 0。
三、动画怎么看
画面里是一排格子，上面有三层信息：
- 绿色色带（格子上方）：当前正在跟踪的子数组
nums[start..end]；
- 金色边框 + 金色横线（格子下方）：历史最优区间
nums[bestStart..bestEnd]；
- 横幅：左边是
cur（当前这段的和），中间是 best，右边是最优值。
最值得盯的是两次"重置"（第 1 帧和第 3 帧）：色带会突然缩短，而被扔掉的那几格变成
灰色虚线 —— 那就是"负资产被扔掉"的动作。第一次扔掉的是
[-2]（一格），第二次扔掉的是
[1, -3]（两格）。
第 6 帧（i = 6）是全场高潮：色带扩到
[3..6]，
cur 到达
6，金色最优区间也推进到
[3..6] —— 从此再没被超过。
四、完整推演表（10 帧逐帧）
输入
nums = [-2,1,-3,4,-1,2,1,-5,4]，答案
6，子数组
[4,-1,2,1]。
几个值得单独拎出来的观察：
帧 2 是"接上之后立刻变负"的典型。
cur 从
1 接上
-3 变成
-2 —— 这一帧本身没重置（因为接上时
cur = 1 >= 0），但接完就变成了负资产，于是下一帧立刻重置。
"接上的决定"和"值不值得"是两回事：接上是因为当时不亏，扔掉是因为接完变负了。
帧 7、8 是"best 不再刷新"的典型。
cur 虽然还在波动（
6 → 1 → 5），但始终没超过
6。注意
cur 在帧 8 回到了
5 —— 如果数组再多一个
2，答案就会变成
7。Kadane 的
cur 永远"蓄势待发"。
帧 1 和帧 3 的重置对象不同：第一次扔掉一格（
[-2]），第二次扔掉两格（
[1,-3]）。重置的粒度完全由"
cur 何时变负"决定，没有人工参数。
五、为什么 cur < 0 就敢扔掉前面整段
这是本题真正的面试考点。反着问更清楚：
扔掉前面整段，难道不会扔掉最优解吗？
不会。论证只需要一句话：
如果前面那段是负的（cur < 0），那么任何以 i 结尾、并且包含前面那段的子数组，都比"只从 i 开始"的子数组更差 —— 因为它们都多背了一个负数。
展开说：设
cur < 0，考察任何形如
[前面某段] + nums[i..j] 的候选。它的和 =
cur + (nums[i..j] 的和)，而
nums[i..j] 的和 是一样的 —— 所以
带上 cur 的版本一律比不带的小。也就是说：
在"以 i 结尾"的这批候选里，最优的那个一定不包含前面的负段。
而 DP 的定义保证我们只关心"以
i 结尾"的最优 —— 扔掉负段不会漏掉任何可能性，因为
最优解要么在前面已经记进 best 了（它的结尾在 i 之前），要么从 i 重新开始。两头都照顾到了。
一句话记法：
cur 是"必须以 i 结尾"这个约束下的最优；扔掉负段，只是在维护这个约束下的最优而已。
六、分治解法：四个量与信息合并
分治把数组从中间劈开，答案只有三种来源：
① 完全在左半边
② 完全在右半边
③ 跨越中点（左半边的后缀 + 右半边的前缀）
麻烦在于 ③ —— "左半边的最大后缀和"没法从"左半边的最大子数组和"推出来。所以分治解法给每个区间
多记三个量，合起来是四元组：
i_sum = 区间总和
l_sum = 以左端点开头的最大子数组和（最大前缀）
r_sum = 以右端点结尾的最大子数组和（最大后缀）
m_sum = 区间内的最大子数组和
合并公式（左区间 L、右区间 R）：
i_sum = L.i_sum + R.i_sum
l_sum = max(L.l_sum, L.i_sum + R.l_sum) # 要么不跨界，要么全吃左区间再接右边的最大前缀
r_sum = max(R.r_sum, R.i_sum + L.r_sum) # 对称
m_sum = max(L.m_sum, R.m_sum, L.r_sum + R.l_sum) # 三种来源：在左 / 在右 / 跨中点
def maxSubArrayDivide(nums):
def get(l, r):
if l == r:
s = nums[l]
return (s, s, s, s) # (l_sum, r_sum, i_sum, m_sum)
mid = (l + r) // 2
L = get(l, mid)
R = get(mid + 1, r)
i_sum = L[2] + R[2]
l_sum = max(L[0], L[2] + R[0])
r_sum = max(R[1], R[2] + L[1])
m_sum = max(L[3], R[3], L[1] + R[0])
return (l_sum, r_sum, i_sum, m_sum)
return get(0, len(nums) - 1)[3]
：很多资料写
O(n log n)。严格按主定理算，合并是常数次比较（
O(1)），递归树共
2n - 1 个节点，所以
T(n) = 2T(n/2) + Θ(1) = Θ(n) ——
和 Kadane 同阶。
O(n log n) 是"朴素分治"的复杂度（每层合并都重新扫一遍区间求跨界最大值）；带四元组缓存之后，合并降到
O(1)，整体就是
O(n)。它的价值从来不在速度 —— 常数比 Kadane 大、还要
O(log n) 的栈空间 —— 而在
可扩展性：
这四个量正是线段树维护的东西。 把题目改成"支持单点修改、随时询问区间最大子数组和"，Kadane 直接报废，而这套分治改一改就是一棵线段树：单点修改 O(log n)、区间查询 O(log n)（合并时沿路径向上推四元组）。
一句话：
Kadane 一次性算完就丢，分治把"合并规则"存了下来 —— 前者是算法，后者是数据结构。
七、变体一：LC 918 环形版 —— 把同一个算法反着用
环形数组里子数组可以"绕圈"。直接想会晕，但按"绕不绕"分类，答案只有两种来源：
① 不绕圈：就是普通的最大子数组和 → Kadane
② 绕圈： 子数组 = 整个数组 − 中间被挖掉的那段
要让绕圈那部分的和最大，就要让挖掉的中间段最小 → 最小子数组和
[ part1 | 被挖掉的最小段 | part2 ]
←────────── total ──────────→
绕圈和 = part1 + part2 = total − minSum
—— 所以"挖掉最小的连续段"就是"最小子数组和"，而这正是 Kadane 把
max 换成
min 的版本。同一个算法，反着用一遍：
def maxSubarraySumCircular(nums):
total = 0
cur_max = max_sum = nums[0]
cur_min = min_sum = nums[0]
for x in nums:
cur_max = max(x, cur_max + x)
max_sum = max(max_sum, cur_max)
cur_min = min(x, cur_min + x)
min_sum = min(min_sum, cur_min)
total += x
if max_sum < 0:
return max_sum # 全负数：绕圈方案会挖空整个数组，不合法
return max(max_sum, total - min_sum)
。全负时最小的连续段就是
整个数组，
total - minSum = 0 —— 那对应一个
空子数组，而题目要求至少含一个元素。所以必须特判：全负时直接返回普通 Kadane 的结果（最大的那个负数）。
[-3,-2,-3] → minSum 是整个数组(-8)，total - minSum = 0（空！）→ 必须返回 maxSum = -2
[5,-3,5] → minSum 是 [-3]，total - minSum = 10 → 环形子数组 [5,5]，答案 10
初始化也同理：
max_sum、
min_sum 都要从
nums[0] 起步而不是 0 —— 全负时"最佳答案是单个负数"，从 0 起步会错。
八、变体二：一串同族题
121 那个联系最值得记住：股票问题"某天买入、之后某天卖出"的最大利润，就是
相邻两天差价数组的最大子数组和。见过这个转化之后，"买卖股票"系列的 DP 就不再是独立的题，而是 Kadane 换了一身衣服。
九、Java 版
class Solution {
public int maxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}
}
十、复杂度
O(n) 是理论下界：任何一个算法都至少要把每个元素看一遍。Kadane 已经贴着下界了。
十一、边界情况与常见坑
边界情况
常见坑
坑 1：cur 和 best 从 0 起步
子数组至少含一个元素。全负数组（如
[-3,-1,-2]）的正确答案是
-1，从 0 起步会错答成 0。
必须从 nums[0] 起步。
坑 2：把"重置"写成 cur <= 0
cur == 0 时"接上"和"重起"的
和一样，但
区间不一样 —— 写
<= 会把起点白白提前，返回的子数组可能带上一段无用的零前缀。判据严格写
< 0（"前面那段是负资产"才扔）。
坑 3：918 忘了全负数特判
total - minSum 在全负时等于 0（空子数组）。少这一行，
[-3,-2,-3] 会错答成
0 而不是
-2。判断方式两种都行：
maxSum < 0 或
minSum == total。
坑 4：918 的 max_sum、min_sum 从 0 起步
同坑 1 —— 全负时环形版的普通分支就是唯一合法答案，起步值错了整题就错。
坑 5：152 乘积版照抄 Kadane 只维护一个值
乘法里负负得正：当前最小值（一个负数）乘上新负数可能变成全局最大。必须
同时维护"以 i 结尾的最大乘积"和"以 i 结尾的最小乘积" 两个量。
坑 6：认为分治是 O(n log n)
合并四元组是
O(1)，递归树
2n - 1 个节点，总计
O(n)。
O(n log n) 是朴素分治（合并时重新扫区间）的账。面试时算清楚这一步，比背复杂度表高一档。
十二、面试怎么答
-
先给 DP 定义："
cur 表示以当前位置结尾的最大子数组和。这个'结尾'是关键 —— 它让转移只有两种可能：接上前面的，或从自己重新开始。"
-
写代码时点破那句话："
cur = max(x, cur + x) 整句只在问：带上前面那段，是赚了还是亏了？cur < 0 就是亏，扔掉重起。"
-
主动回答正确性（多数人跳过这步）："扔掉前面整段不会漏解 —— 前面为负时，任何包含它的候选都比不包含的差，所以'以 i 结尾'的最优一定不含负段；而更早的最优已经记在
best 里了。"
-
如果被追问返回子数组本身："把
max 写成 if cur < 0 的形式，重置时记 start = i，刷新 best 时记 bestStart/bestEnd。值视角和位置视角是同一件事的两种写法，但位置只存在于后者。"
-
如果被追问分治："每个区间记四个量：最大前缀、最大后缀、总和、最大子数组和。合并公式四条，
m_sum 的三种来源对应'在左 / 在右 / 跨中点'。合并 O(1)、节点 O(n)，总计 O(n) —— 它的价值是能升级成线段树，支持单点修改。"
-
如果被追问环形版："绕圈的子数组等于整个数组挖掉中间一段；挖得越少越好 → 挖掉最小子数组和。所以正反各跑一遍 Kadane。全负时要特判 —— 那时挖掉的是整个数组，剩下的是空子数组，不合法。"
-
如果被追问 121："股票的最大利润就是相邻差价数组的最大子数组和。同一个算法换了身衣服。"
结语
最大子数组和是那种"代码越短、越见功力"的题。
Kadane 的五行代码里，
cur = max(x, cur + x) 只有一个决策点，但它背后是三个层次的东西：
表层：两个候选取大。
DP 层：cur 是"以 i 结尾"这个约束下的最优 —— "结尾"二字让转移从 O(n²) 种坍缩成 2 种。
贪心层：前面那段为负时，它在"以 i 结尾"的所有候选里都是纯负担 —— 扔掉它不丢任何可能性。
而分治和环形版各自从另一个方向切进来：分治说"把合并规则存下来，就能反复回答"（于是有了线段树）；环形版说"把同一个算法反着用，绕圈就变成了挖洞"。
最后自测一下，特别是全负数和单元素这两个"答案不是 0"的边界：
assert maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6 # 官方例
assert maxSubArray([-3, -1, -2]) == -1 # 全负：不是 0
assert maxSubArray([1]) == 1 # 单元素
assert maxSubArray([5, 4, -1, 7, 8]) == 23 # 全正整段
assert maxSubarraySumCircular([5, -3, 5]) == 10 # 环形 [5,5]
assert maxSubarraySumCircular([-3, -2, -3]) == -2 # 环形全负特判
这几行比跑十遍官方样例有用。