题面：要一个和，不要一段区间
LeetCode 53「最大子数组和」（Maximum Subarray）的题面一句话就能说完：给你一个整数数组 nums，找出一个和最大的连续子数组（子数组最少包含一个元素），返回其最大和。注意返回的是那个和，不是左右端点——区间本身只是求解过程中的中间产物。
三个官方示例：
nums = [-2,1,-3,4,-1,2,1,-5,4]，输出6（子数组[4,-1,2,1]）；nums = [1]，输出1；nums = [5,4,-1,7,8]，输出23。
约束（2026-10-07 从力扣官方题目页核对）：1 <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4。两个细节值得圈出来：一是数组含负数，而且可能全负——所以答案可能是负的，「不选任何元素得 0」是非法解；二是长度到 10^5，O(n²) 起步就要擦边超时。题目还有一句进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
从暴力讲起：重复在哪
最直白的写法是枚举所有区间：固定左端点 i，让右端点 j 从 i 向右扫，边扫边累加，记下见过的最大和。内层累加复用了前一步的和，单个左端点是 O(n)，整体 O(n²)：
def max_subarray_brute(nums: list[int]) -> int:
best = None
for i in range(len(nums)):
s = 0
for j in range(i, len(nums)):
s += nums[j]
best = s if best is None else max(best, s)
return best
它错在哪儿？没错，只是慢。更值得问的是：重复在哪。比如 [3..7] 这一段的和，会被 i = 1, 2, 3 的三轮枚举各加一遍；但从「能否拼出更优解」的角度看，这些重复劳动没有回答任何新问题——每轮枚举只知道自己这个左端点的最好情况，不知道这段区间接在谁后面更好。暴力把所有区间都算了一遍，却没沉淀下任何可复用的信息。动态规划的入场券，就是找到那个值得沉淀的状态。
关键一步：dp[i] 是「以 i 结尾」，不是「前 i 个」
很多人第一次写这题会定义 f(i) = 前 i 个元素里的最大子数组和，然后卡死：知道前 i-1 个的答案，新来的 nums[i] 要不要接上去？接到哪一段后面？不知道——因为 f(i-1) 只记了答案，没记那个最优子数组贴不贴着右端。全局型的状态天生缺一个「位置锚点」，转移无从谈起。
正确的定义只差一步：dp[i] = 以 nums[i] 结尾（必含 nums[i]）的所有子数组中的最大和。转移变得一眼可见：
dp[i] = max(nums[i], dp[i-1] + nums[i])
nums[i] 要么自起炉灶（前面的 dp[i-1] 是负贡献，掐掉重开），要么延续上一个结尾的最好阵营。为什么这个定义是对的？因为「以 i 结尾的子数组」去掉最后一个元素后，恰好是「以 i-1 结尾的子数组」——子问题与原问题同构，最优子结构和无后效性都齐了。而最终答案是 max(dp[i]) 而不是 dp[n-1]：最优子数组一定以某个位置结尾，逐位置取最大就是把所有候选收齐。
这就是标题里说的「一步之遥」：从「前 i 个的最大」到「以 i 结尾的最大」，状态定义里多锚定了一个位置，转移就从无解变成 O(1)。动态规划里最常见的失败，不是转移方程写错，而是状态里少了一维必要的信息。
压到 O(1)：Kadane 形式
dp[i] 只依赖 dp[i-1]，整行数组可以压成两个变量：cur 滚动当前结尾的最优值，best 顺路维护全局答案。这就是 Kadane 算法——时间 O(n)，空间 O(1)：
def maxSubArray(nums: list[int]) -> int:
# cur：以当前元素结尾的最大子数组和；best：全局答案
# 初始化用 nums[0] 而不是 0：子数组至少含一个元素，全负数时答案必须是负的
cur = best = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # 自起炉灶，还是延续前面的阵营
best = max(best, cur)
return best
最容易踩的坑藏在初始化里：cur = best = 0 是错的。它隐含「允许空子数组」，可题面要求至少含一个元素——对全负数组 [-8,-3,-6,-2,-5,-4]，正确答案是 -2（只取单个 -2），初始化为 0 会输出 0。用 nums[0] 初始化，再从第二个元素扫起，这个边界就自然消掉了，全负、单元素、全正三种情形都不用特判。
顺带一段历史：这个问题由 Ulf Grenander 于 1977 年作为数字图像模式估计的简化模型提出，Michael Shamos 一夜之间给出 O(n log n) 的分治解，而 Jay Kadane 在卡内基梅隆的算法研讨会上大约一分钟就给出了线性解；经 Jon Bentley 1984 年在《Communications of the ACM》的「Programming Pearls」专栏传播，它成了教科书级的动态规划入门案例（据 Wikipedia「Maximum subarray problem」条目）。
进阶：分治 O(n log n)
分治的思路：把区间 [lo, hi] 从中点劈开，左半、右半各自递归，再合并跨中点的候选。关键在于每个区间不能只汇报一个最大子数组和，要汇报四个量：
m：区间内的最大子数组和（不限制位置）；p：必须含左端点的最大前缀和；s：必须含右端点的最大后缀和；t：区间总和。
合并规则：跨中点的子数组 = 左半的某个后缀 + 右半的某个前缀，所以 m = max(左m, 右m, 左s + 右p)；前缀要么整体在左半，要么吞掉整个左半再接右半的前缀，即 p = max(左p, 左t + 右p)；后缀对称；总和直接相加：
def maxSubArrayDC(nums: list[int]) -> int:
def solve(lo: int, hi: int) -> tuple[int, int, int, int]:
# 返回 (区间最大子数组和, 最大前缀和, 最大后缀和, 区间总和)
if lo == hi:
v = nums[lo]
return v, v, v, v
mid = (lo + hi) // 2
lm, lp, ls, lt = solve(lo, mid)
rm, rp, rs, rt = solve(mid + 1, hi)
best = max(lm, rm, ls + rp) # 跨中点：左半最大后缀接右半最大前缀
prefix = max(lp, lt + rp)
suffix = max(rs, rt + ls)
return best, prefix, suffix, lt + rt
return solve(0, len(nums) - 1)[0]
单看这道题，O(n log n) 不如 Kadane；但这套「每区间维护四元组 + 线性合并」的结构，正是线段树维护区间最大子段和的标准姿势——支持单点修改、任意区间查询的最大子段和问题，每个结点的 merge 函数就是上面这四行。分治版本是理解它的最好台阶。
验证：三种写法对拍
以上三份代码（暴力、Kadane、分治）在本地用同一套用例对拍，全部通过：
- 边界用例：全负数
[-8,-3,-6,-2,-5,-4]三者一致得-2；单元素[-7]得-7、[5]得5；全正数[1,2,3,4,5]得15；官方三示例得6 / 1 / 23。 - 随机对拍 1000 轮：数组长度取
[1, 60]、元素值域取题面约束[-10^4, 10^4]，三种解法结果全部一致。 - 规模冒烟：按题面上限生成
n = 10^5的随机数组，Kadane 与分治结果一致。
日常写题时，O(n²) 暴力是最值得留着的「对拍基准」——它慢，但它对。
延伸一分钟
- 股票买卖（LeetCode 121）：把价格数组转成相邻差价
diff[i] = prices[i] - prices[i-1]，一次买卖的最大利润就是diff的最大子数组和。prices = [7,1,5,3,6,4]对应diff = [-6,4,-2,3,-2]，最大子数组和4-2+3 = 5正是答案。「维护历史最低价」的经典写法与 Kadane 逐步等价：舍掉负前缀，就是更新历史最低。 - 前缀和视角：设
P[i]为前i个元素之和，子数组[i+1..j]的和就是P[j] - P[i]，于是最大子数组和等于「最大前缀和减去它之前的最小前缀和」——扫一遍维护历史最小前缀即可，与 Kadane 异曲同工。同一个问题，锚点选在哪，解法就长成什么样。
读者留言
COMMENTS 暂无还没有留言，来说第一句？