什么是 Kadane 算法？#

Kadane 算法是解决最大子数组和问题的经典算法，由 Jay Kadane 于 1984 年提出。它能在 $O(n)$ 时间、$O(1)$ 空间内找到数组中的最大连续子数组和。

它的核心代码极为简短：

1
def max_subarray(nums):
2
    ans = float('-inf')
3
    pre = 0
4
    for x in nums:
5
        pre = max(pre, 0) + x
6
        ans = max(ans, pre)
7
    return ans

寥寥几行，却浓缩了动态规划和贪心两种思想的精髓。接下来我们逐步拆解它背后的原理。

核心直觉#

想象你是一个股民，每天都有盈亏。你需要在某一天买入、之后某一天卖出，获得最大收益——这就是著名的最大利润问题，本质上就是最大子数组和。

Kadane 算法的核心直觉可以浓缩为一句话：

💡 核心直觉：在遍历数组时，我们始终面临一个选择——是延续之前的累加（pre + x），还是重新开始（x）。做这个选择的依据很简单：如果之前的累加是正数，它对我们有帮助，保留它；如果之前的累加是负数或零，它只会拖后腿，丢弃它。

🧠 换个角度：一个负数的前缀，就像背着一个越来越重的包袱爬山——越早扔掉它，越早轻装上阵。Kadane 算法的 max(pre, 0) 就是这个”扔包袱”的动作。

从动态规划的角度理解#

1
pre = max(x, pre + x)

1
pre = max(pre, 0) + x

从贪心角度理解#

换个视角，Kadane 算法也可以看作一种在线贪心：

🧠 贪心视角：我们一边扫描数组，一边维护”当前正在考虑的子数组”。每遇到一个新元素，我们就问自己——这个元素加入后，子数组和是变大了还是变小了？如果变小了（前缀和为负），说明前面的元素全是累赘，“咔嚓”一刀切断，从当前元素重新开始。

这里的贪心选择是局部最优的——在每一步，我们都选择”使当前子数组和最大”的决策。但这之所以能找到全局最优，是因为任何全局最大子数组不可能包含一个和为负的前缀（否则去掉这个前缀会得到一个更大的子数组）。

💡 贪心安全性的证明：假设全局最大子数组是 $nums[L..R]$，其中 $L$ 之前有一个和为负的前缀 $nums[k..L-1]$。那么 $nums[L..R]$ 的和一定大于 $nums[k..R]$ 的和（因为负前缀拉低了总和）。因此 Kadane 算法在 $L$ 位置”丢弃”前一个负前缀的决策，恰好保留了真正的最优解。

为什么 Kadane 算法同时属于 DP 和贪心？#

这不是巧合。很多优秀的算法都跨越了多种设计范式：

Kadane 算法之所以能被两种范式同时解释，是因为它的贪心选择恰好也是 DP 的最优子结构——“丢弃负前缀”这个贪心动作，在 DP 的转移方程中被验证为总是最优的。

💡 什么时候贪心和 DP 重合？ 当 DP 的状态转移只涉及”取或不取”的二元选择，且其中一种选择总是被另一种支配时（如”加负数前缀”总是被”丢弃它重新开始”支配），DP 就退化为了贪心。Kadane 正是这类”DP 退化为贪心”的经典案例。

执行过程可视化#

以 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例，追踪 Kadane 算法的每一步决策：

注意 $i = 0, 1, 3$ 三个位置都触发了”丢弃”：

• $i=0$：前面是 0（等效于没有前缀），取 -2。
• $i=1$：pre = -2，是负数，丢弃前面的 [-2]，从 1 重新开始。
• $i=3$：pre = -2，是负数，丢弃前面的 [1, -3]，从 4 重新开始。而 $i=4$ 到 $i=6$ 连续保留，构建出最优解 $[4, -1, 2, 1]$（和为 6）。

💡 这个表揭示了 Kadane 算法的运作规律：“丢弃”多发生在遇到负数前缀或数组开头的地方。一旦 pre 转正，算法就会贪婪地一直累加（即使遇到负数也加，因为正前缀总体上还是赚的），直到前缀和再次归零或转负。

变体与扩展#

1
def max_subarray_with_indices(nums):
2
    ans = float('-inf')
3
    pre = 0
4
    start = end = 0        # 最优子数组的起止位置
5
    cur_start = 0           # 当前 pre 的起点
6

7
    for i, x in enumerate(nums):
8
        if pre <= 0:
9
            pre = x
10
            cur_start = i   # 丢弃前缀，重新标记起点
11
        else:
12
            pre += x
13

14
        if pre > ans:
15
            ans = pre
16
            start = cur_start
17
            end = i
18

19
    return nums[start:end + 1], ans

总结#

Kadane 算法虽然只有短短几行代码，但它身上凝聚了几个非常重要的算法设计思想：

1. 强制结尾的 DP 状态定义：$dp[i] = \text{以 i 结尾的最优解}$，这是子数组类 DP 的万能钥匙。
2. 空间优化的来源识别：$dp[i]$ 只依赖 $dp[i-1]$ → 滚动变量 → $O(1)$ 空间。
3. DP 退化为贪心：当状态转移中的一种选择被另一种严格支配时，DP 可以简化为贪心决策。
4. 分治视角：跨越中点的最大和 = 左半后缀最大 + 右半前缀最大，这直接导向线段树的节点合并。

💡 推荐练习顺序：最大子数组和（本题）→ 乘积最大子数组 → 环形子数组的最大和 → 线段树区间最大子段和。这个序列将 Kadane 算法的思想逐步泛化，覆盖了 DP、贪心、分治、线段树四个领域。

掌握了 Kadane 算法，你掌握的不仅仅是一道题，而是一整套处理”子数组最值”问题的思维框架。