LeetCode 53. 最大子数组和：Kadane 算法的一行核心

题目与暴力的困境

LeetCode 53：给定整数数组（含负数），找出和最大的连续子数组（至少一个元素），返回最大和。

输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6（子数组 [4, -1, 2, 1]）

暴力 O(n²)：枚举所有子数组起点与终点（两层循环）——「子数组」的数量是 n(n+1)/2——前缀和优化到 O(n²)（前缀和相减——「前缀和」是子数组问题的通用工具——但 O(n²) 在 n=10⁵ 时是 10¹⁰——超时。优化的方向：「子数组和的什么性质没有被利用？」——答案是「连续」——连续意味着「子数组以 i 结尾的和」可以由「以 i-1 结尾的和」递推——这就是 DP 的入口。

Kadane 算法：一行核心的推导

状态定义：dp[i] = 「以 nums[i] 结尾」的最大子数组和——「以 i 结尾」是关键限定——不是「前 i 个元素中的最大子数组和」——「为什么必须以 i 结尾」：转移方程需要「子数组的连续性」（以 i 结尾的子数组 = 以 i-1 结尾的子数组 + nums[i]，或只有 nums[i]——「连续性」让相邻状态产生联系——如果定义成「前 i 个的最大」（无位置限定）——与 dp[i-1] 之间没有推导关系——「状态定义的连续限定」是这道题 DP 的成败关键——与爬楼梯的状态定义思想一脉相承（「dp[i] 要回答一个可递推的问题」）。

转移方程：「以 i 结尾的最大子数组和」只有两种来源：延续前面的（dp[i-1] + nums[i]）或从自己重新开始（nums[i]）——选大的：

dp[i] = max(dp[i-1] + nums[i], nums[i])

「这一行的直觉翻译」：「前面的累积和如果是负的，就扔掉它——负数只会拖累我」——「扔掉负资产、重新开始」——这就是 Kadane 算法的全部智慧——答案：max(dp)（所有以 i 结尾的最大值中取最大——「答案不一定以 n 结尾」——所以要求全体的 max）。

def max_sub_array(nums):
    dp = nums[0]
    ans = dp
    for i in range(1, len(nums)):
        dp = max(dp + nums[i], nums[i])   # 核心一行
        ans = max(ans, dp)                # 全局最大
    return ans

graph TD
    A[状态: dp[i] = 以 i 结尾的最大子数组和] --> B[转移: max(dp[i-1]+nums[i], nums[i])]
    B --> C[直觉: 前面的和是负的就扔掉]
    A --> D[答案: max(dp[0..n-1])<br/>最大子数组不一定以 n 结尾]

「逐个追踪」（[-2, 1, -3, 4, -1, 2, 1, -5, 4]）：dp[-2]=-2 → dp[1]=max(-2+1,1)=1（扔掉 -2）→ dp[-3]=max(1-3,-3)=-2 → dp[4]=max(-2+4,4)=4（扔掉负的和）→ dp[-1]=3 → dp[2]=5 → dp[1]=6 → dp[-5]=1 → dp[4]=5——「扔掉的动作」出现在「dp[i-1] < 0」的每一个时刻——ans 全程追踪最大——6。

贪心视角：另一种理解

「Kadane 也是贪心」：换一个视角——「遍历数组，累加当前和；当前和一旦为负，清零重新开始」：

def max_sub_array(nums):
    ans = nums[0]
    cur = 0
    for x in nums:
        cur = max(cur + x, x)    # 与 dp 同一行
        ans = max(ans, cur)
    return ans

「为什么清零是贪心正确的」：当前和为负时——「保留它对后续任何子数组都是拖累」（后续任何以「从这里开始」的子数组，去掉这段负前缀只会更大）——「负前缀不可能有帮助」的证明——「贪心正确性」的证明思路（交换论证——「贪心与 DP 的关系」：这道题的贪心与 DP 转移方程完全相同——「dp[i] = max(dp[i-1]+x, x)」的贪心解读——「贪心是 DP 的特例」（当转移方程只有「取/不取」的局部最优判断时——「贪心与 DP 的边界」——能证明贪心正确就用贪心（更简单），证明不了就用 DP（更通用）——「这道题是学习两者关系的绝佳样本」。

变体的思考：「返回子数组本身」（不只和——记录起止下标（「下标的追踪」：dp 重开时记录新起点、ans 更新时记录终点——「最大乘积子数组」（LeetCode 152——「负数的翻转」（乘法中负负得正——同时维护最大与最小——「dp 状态的扩展」——一个最大不够、要最大+最小——「152 是 53 的进阶姊妹篇」）。「环形数组」（LeetCode 918——「环形 = 拆解」（最大子数组和 = max(普通最大, 总和 - 最小子数组和)——「环形问题的拆解套路」。

Kadane 的进阶：DP 状态的设计原则与变体矩阵

Kadane 的进阶：DP 状态设计的原则总结与变体矩阵的系统梳理。「DP 状态设计的原则」：「原则一：状态的完备性」——「dp[i] 要回答『到 i 为止』的完整问题」——「完备性」的检验（转移方程能否只用已定义的状态表达——「完备性的反例」（缺位置信息的 dp——「补信息」的方法（状态加维度——「二维 dp」（加「结尾」信息——「状态维度」的膨胀——「维度的控制」（只加必要的——「完备性与复杂度」的权衡。「原则二：转移的闭合性」——「转移只引用已算的状态」（拓扑序——「拓扑序」：状态的依赖图无环——「环的出现」意味着状态设计错误——「无环」的检查——「原则三：边界的完整性」——「dp[0] 或 dp[1]」的完整——「边界的缺失」导致转移引用未定义状态——「三个原则」的检验顺序——「写 DP 前过三原则」——「原则」是 DP 不出 bug 的第一道防线。「Kadane 的变体矩阵」：「变体一：最大乘积子数组（152）」——负负得正——「双状态：最大+最小」——「负数翻转」（max 与 min 交换——「零的处理」（乘积归零——「双 dp 的转移」（「三选一：max、min、nums[i]」——「变体二：环形最大子数组（918）」——「拆解」（环形 = 直线 max OR 总和-直线 min——「min 的必要性」——「全负数」的边界（总和-min=0 的陷阱——「全负数的特殊处理」——「变体三：两个不重叠子数组的最大和」——「前后缀分解」（左边最大+右边最大——「前后缀数组」的预处理——「枚举分割点」——「变体矩阵的总结」：「53 → 152（乘法翻转）→ 918（环形拆解）→ 不重叠（前后缀）」——「每个变体引入一个新思想」——「变体链的学习路径」——「Kadane 是这条链的起点」。Kadane 的进阶总结：DP 状态设计的三原则（完备性、转移闭合、边界完整）+变体矩阵（乘积/环形/不重叠的三个新思想）——「Kadane」的真正价值：它是「DP 状态设计」的入门沙盘——「状态的完备性」设计错了，后面全错——「学 Kadane 学的不是一行公式，是状态设计的思维」——**「一行公式背后是状态设计的完整方法论」——这个方法论将从爬楼梯延伸到背包、编辑距离、直到树形 DP。

Kadane 的高频问答：全负数组、状态定义错误与下标追踪

问题一：数组全是负数时答案是什么？为什么初始化必须用 nums[0] 而不是 0？——全负数组（如 [-3, −1, −2]）的答案是 −1：子数组至少包含一个元素，最大子数组就是其中最大的单个元素。这直接决定了初始化方式：ans 与 dp 都从 nums[0] 起步、循环从下标 1 开始——习惯性初始化为 0 的话，全负输入会错得成 0，等于默认「可以选空子数组」，与题意直接冲突。「至少一个元素」这六个字是 53 题的隐藏考点——读题时把「至少」「最多」「连续」这类限定词圈出来，比多刷三道题更有用：限定词就是出题人埋的边界，每一个都对应一处代码防御。

问题二：dp[i] 定义成「前 i 个数中的最大子数组和」行不行？——不行，这是本题最典型的状态定义错误：前 i 个的最大值与前 i−1 个的最大值之间写不出递推关系——新的最大子数组可能在任何位置开始，转移断了。正确定义必须带「以 i 结尾」的位置限定，转移才闭合：以 i 结尾只有两种来源，延续前面的或从自己重开。如果觉得「以 i 结尾」不直观，等价的写法是双变量：cur 表示以当前位置结尾的最优值（局部量）、ans 维护历史最优（全局量）——「局部 + 全局」与「dp 数组 + max(dp)」完全等价，但双变量更能传达 Kadane 的直觉，也更贴近滚动变量的最终形态。状态定义的通用纪律：宁可多带限定，也不能让转移断了——发现推不动转移时，第一反应永远是「我的状态少了什么信息」，而不是「换个技巧试试」。

问题三：要同时返回子数组的起止下标，代码怎么改？——在两个时刻做记录：dp 重开时（dp[i−1] < 0，延续只会拖累）把候选起点暂设为 i；ans 刷新时把候选起点定稿为 start、当前位置记为 end。两个易错点：一是相等时的取舍——dp[i−1] + nums[i] == nums[i]（即 dp[i−1] == 0）时重开与延续都正确，但重开得到的子数组更短，若题目要求最短解就选重开；二是更新顺序——先判断重开、再更新 ans，顺序颠倒会让 start 指向旧值。这个变体在面试的出现率不低，它考的不是新算法，是你是否真正理解 dp 重开时刻的物理含义——背公式的人答不出下标，理解重开的人顺手就写对了。

问题四：Kadane 能流式化或并行化吗？——流式天然支持：cur 与 ans 两个变量随数据流入更新，O(1) 状态、数据只过一遍不回头——这就是「在线算法」的教科书形态，监控系统的「近 N 秒最大涨幅」类指标用的正是这个形态。并行化有经典拆法——分治：区间 [l, r] 用四个量完整描述（区间总和、区间内最大前缀和、最大后缀和、区间最大子数组和），左右两半的四个量可以 O(1) 合并成父区间的四个量——线段树每个节点维护这组量，就得到了「支持单点修改的最大子数组和查询」，是竞赛与面试都认的经典拓展。Kadane 是线性扫描的形态，分治是可合并的形态——同一个问题的两种数据结构化，也再次呼应了「DP 状态的完备性」：四个量缺一个，合并就断。

小结

最大子数组和的完整解析：状态定义的关键（dp[i] = 以 i 结尾的最大子数组和——连续限定让递推成立——状态定义是成败关键）；一行核心（dp[i] = max(dp[i-1] + nums[i], nums[i])——前面的和是负的就扔掉）；贪心视角（当前和为负清零——负前缀不可能有帮助的证明——贪心是 DP 的特例）；变体（返回下标、最大乘积（维护最大+最小）、环形数组（拆解））。给学习者的方法论：Kadane 是「从暴力到 DP」的最佳练习题——暴力 O(n²) 的解法人人会写——「利用『连续』性质找到递推关系」是优化的突破口——以及状态定义的教训：dp[i] 必须带「以 i 结尾」的限定——少了这个限定，DP 就断了——状态定义的精确性，是 DP 从「会写」到「写对」的分界线。

Kadane 算法的一行核心教给我们的：「负资产要及时止损」——在数组里如此，在人生里也如此——从负的地方重新开始，永远好过被它拖到底。