0053-maximum-subarray.md

53. 最大子数组和

项目	内容
链接	LeetCode CN
标签	数组 · 动态规划 · Kadane
源码	0053-maximum-subarray.py

---

一、题目理解

题意

找连续子数组的最大和。至少取一个元素。

示例

输入	输出	最优子数组
[-2,1,-3,4,-1,2,1,-5,4]	6	[4,-1,2,1]
[1]	1	[1]
[5,4,-1,7,8]	23	整个数组

Kadane 核心思想

若当前前缀和变负，丢弃从头再来——负前缀只会拖累后续。

flowchart LR
    A["curr += num"] --> B["pre_max = max(pre_max, curr)"]
    B --> C["curr = max(curr, 0)"]
    C --> A

Loading

---

二、思路总览

变量	含义
curr_sum	以当前位置结尾的最大子数组和（前缀 ≤0 则归零）
pre_max	全局最大和

步骤	做什么
1	curr_sum += num
2	pre_max = max(pre_max, curr_sum)
3	curr_sum = max(curr_sum, 0) — 负则丢弃

---

三、解法演进

方法一：Kadane 单变量

变量名 nozero_prefix 即当前子数组和，本质是 Kadane。

模拟 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：

num	curr（加后）	pre_max	curr（归零后）
-2	-2	-2	0
1	1	1	1
-3	-2	1	0
4	4	4	4
-1	3	4	3
2	5	6	5
1	6	6	6
-5	1	6	1
4	5	6	5

方法二：DP 定义（等价写法）

dp[i] = max(nums[i], dp[i-1] + nums[i])，可压缩为单变量。与 Kadane 完全等价。

# DP 形式（未采用，仅作对照）
dp = nums[0]
ans = dp
for num in nums[1:]:
    dp = max(num, dp + num)
    ans = max(ans, dp)

---

四、实现代码

from math import inf
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = 0
        pre_max = -inf
        for num in nums:
            curr_sum = curr_sum + num
            pre_max = max(pre_max, curr_sum)
            curr_sum = max(curr_sum, 0)
        return pre_max

---

五、复杂度

指标	值
时间	O(n)，一次遍历
空间	O(1)

注意：

• pre_max 初值用 -inf，不能为 0（全负数时答案为最大单个元素）
• 先更新 pre_max 再归零 curr_sum，顺序不能反
• 分治解法 O(n log n) 存在，但 Kadane O(n) 更优