最大子数组和（Kadane 算法）

最大子数组和（Kadane 算法）

模板

标准版（DP 转移，推荐）

def kadane(nums):
    cur = nums[0]   # 以 i 结尾的最大子数组和
    best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # 要么自己重开，要么接上前缀
        best = max(best, cur)
    return best

全负数组天然正确（答案 = 最大元素），不需要哨兵值，是三种写法里最不容易出错的。

竞赛 stdin 版（前缀和重置视角）

n = int(input())
a = [int(x) for x in input().split()]

cur = 0  # 以当前位置结尾的最大子数组和
ans = float('-inf')  # 全局最大和
for i in range(n):
    cur += a[i]
    ans = max(ans, cur)
    if cur < 0:
        cur = 0  # 负数没有贡献，重新开始
print(ans)

与前一种行为等价，但有两个易错点：ans 必须初始化为 -inf；必须先更新 ans 再清零 cur（顺序反了会漏掉全负数组的答案）。

允许空子数组版

def kadane_allow_empty(nums):
    cur = 0
    best = 0
    for x in nums:
        cur = max(0, cur + x)
        best = max(best, cur)
    return best

仅当题目允许空子数组（答案 $\ge 0$）时使用。

解释

用途：$O(n)$ 求连续子数组的最大和（LC 53）及其各种变形。

原理：动态规划——cur 表示以当前位置结尾的最大子数组和，转移为「接着前面累加」或「从当前元素重新开始」二者取大。

DP 定义与转移

设 $dp[i]$ 为以 $i$ 结尾的最大子数组和：

$$dp[i] = \max(a[i],\ dp[i-1] + a[i])$$

• 若 $dp[i-1] \ge 0$：前面的累积有贡献，接上更优；
• 若 $dp[i-1] < 0$：负前缀只会拖累，不如从 $a[i]$ 重新开始。

答案为 $\max_i dp[i]$（子数组必须非空，所以不是 $dp[n-1]$）。空间上只需一个滚动变量 cur，故 $O(1)$ 空间、$O(n)$ 时间。

前缀和视角

Kadane 等价于维护「历史最小前缀和」：最大子段和 $= \maxi (\text{pref}[i] - \min{j \le i} \text{pref}[j])$。「负前缀清零」就是在维护这个最小值。这个视角便于推广到带修改的变形（见例题 2）。

变形速查

变形	做法
环形数组最大子段和（LC 918）	$\max(\text{kadane}(a),\ \text{sum}(a) - \text{minkadane}(a))$，注意全负时取前者
最大子段和的起止位置	转移时记录 cur 的起点，更新 best 时保存区间
至多删去一个元素的最大子段和（LC 1186）	前后缀分解：f[i] + g[i+1] 取最大
允许一次区间翻倍	见例题 2，上界 $2 \times \text{kadane}$
恰好 k 个不相交子段的最大和	费用流 / dp[i][j][0/1]

例题

例题 1：LC 53 最大子数组和（模板直接套）

LeetCode 53（中等）：求整数数组中连续子数组的最大和。模板原题，三种写法任选其一即可。

例题 2：加速窗口收益（2 × Kadane）

第2题-加速窗口收益（小红书机考）：可以开一次窗口把一段连续收益翻倍，再取最大连续和。任取答案段 $S$ 与窗口 $W$，总收益 $= \text{sum}(S) + \text{sum}(S \cap W)$，而 $S \cap W$ 也是连续子段、不超过全局最大子段和，故上界为 $2 \times \text{kadane}$，把窗口开在最大子段上即可取到。

例题 3：买卖股票的最佳时机（Kadane 变形）

121. 买卖股票的最佳时机（Hot100/贪心）：一次遍历维护历史最低价、更新最大利润，与「维护历史最小前缀和」的 Kadane 视角同构。

关联

• 滑动窗口 / 双指针笔记：04_滑动窗口