题目要求

输入输出

  • 输入：整数数组 nums
  • 输出：返回连续非空子数组的最大和
  • 子数组必须连续
  • 至少选一个元素
  • 约束：1 <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4

示例

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：[4,-1,2,1] 的和最大，为 6

输入：nums = [1]
输出：1

这篇只用 Python，从 dp[i] 的含义一步一步推出 Kadane 算法。

从 [-2,1,-3,4] 的断点开始

看一个前缀例子：

nums = [-2, 1, -3, 4]

如果走到 4，有两种选择：

  • 把前面的某个连续子数组接到 4 前面
  • 从 4 自己重新开始

这里的关键不是“所有子数组怎么枚举”，而是：

当我们决定一个最优子数组必须以当前位置结尾时，它的来源只有两种：接上前一个位置的最优结尾，或者从当前位置重新开始。

这就是一维 DP 的入口。

Step 1：先定义一个更小的问题

直接问“整个数组的最大子数组和是多少”太大。我们先强加一个限制：

如果子数组必须以第 i 个元素结尾，它的最大和是多少？

这个值记为 dp[i]。

这里的 dp[i] 不是“前 i 个元素里的最大子数组和”。它更窄：

dp[i] = 必须以 nums[i] 结尾的连续子数组最大和

先写最小骨架：

def max_sub_array(nums: list[int]) -> int:
    n = len(nums)
    dp = [0] * n

现在这个版本能做到：

  • 给每个位置预留一个状态。
  • 明确 dp[i] 绑定的是“以 i 结尾”。

它还缺：

  • 第一个位置的值。
  • 后续位置如何从前一个状态转移。
  • 最终答案从哪里取。

Step 2：第一个位置只能选自己

在上一版基础上，先填 base case。

如果子数组必须以 0 结尾，那它只能是：

[nums[0]]

所以新增：

dp[0] = nums[0]

现在代码是：

def max_sub_array(nums: list[int]) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]

现在这个版本能做到：

  • 正确处理第一个位置的“以 0 结尾”状态。

它还缺：

  • i > 0 时的状态转移。
  • 整个数组的答案。

Step 3：当前位置只有“接上”或“重开”两种来源

现在考虑 i > 0。

如果最大子数组必须以 i 结尾，它最后一个元素一定是 nums[i]。它的前面只有两种情况：

  1. 接上一个也以 i - 1 结尾的最优子数组
  2. 不接任何前缀，从 nums[i] 重新开始

所以在上一版基础上新增转移：

for i in range(1, n):
    dp[i] = max(dp[i - 1] + nums[i], nums[i])

这条转移里的两项含义是：

  • dp[i - 1] + nums[i]：接上前一个位置的最佳结尾
  • nums[i]：从当前位置重新开始

现在代码是：

def max_sub_array(nums: list[int]) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]

    for i in range(1, n):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])

现在这个版本能做到：

  • 算出每个位置作为结尾时的最大连续和。

它还缺：

  • 最终答案不一定以最后一个位置结尾。

Step 4：答案是所有 dp[i] 的最大值

上一版算出的 dp[i] 都是“必须以 i 结尾”的局部答案。题目问的是任意位置结尾的最大值。

所以新增：

return max(dp)

得到第一版完整正确代码：

def max_sub_array(nums: list[int]) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]

    for i in range(1, n):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])

    return max(dp)

现在这个版本能做到：

  • 正确返回最大子数组和。
  • 清楚保留每个位置的 dp[i]，适合学习状态含义。

它还缺：

  • 空间还可以优化，因为转移只依赖 dp[i - 1]。

Step 5：慢速走一遍表

用示例：

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

逐步计算：

inums[i]接上 dp[i-1] + nums[i]重开 nums[i]dp[i]
0-2--2-2
11-111
2-3-2-3-2
34244
4-13-13
52525
61616
7-51-51
84545

所以：

max(dp) = 6

这一步要确认的不是表本身，而是 dp[i] 的含义始终没有变：

dp[i] 只回答“必须以 i 结尾”的最大和。

Step 6：把 dp 数组压成两个变量

上一版的瓶颈是空间。

转移：

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

只依赖上一个状态 dp[i - 1]，不需要保留整张表。

把 dp[i - 1] 替换成 cur：

cur = max(cur + x, x)

同时题目最终要的是所有 dp[i] 的最大值，所以保留 best：

best = max(best, cur)

最终完整代码是：

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        cur = nums[0]
        best = nums[0]

        for x in nums[1:]:
            cur = max(cur + x, x)
            best = max(best, cur)

        return best


if __name__ == "__main__":
    print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
    print(Solution().maxSubArray([1]))

现在这个版本能做到：

  • 保持和 dp 表版本相同的转移含义。
  • 把额外空间从 O(n) 降到 O(1)。

它还缺：

  • 如果题目要求返回子数组本身，还需要额外记录起止下标；本题只要求返回最大和。

正确性

不变量：

  • 处理到位置 i 后，cur 等于“必须以 i 结尾的最大连续子数组和”。
  • best 等于“到目前为止见过的最大 cur”。

为什么转移正确：

  • 任何以 i 结尾的连续子数组，要么只包含 nums[i]，要么由某个以 i - 1 结尾的连续子数组接上 nums[i]。
  • 如果要接上前面，接的那段必须是以 i - 1 结尾的最大者，否则可以替换成更大的，得到更优结果。
  • 所以 cur = max(cur + x, x) 覆盖了全部可能来源。

为什么返回 best：

  • 最大子数组可以结束在任意位置。
  • 每个结束位置的最优值都会成为某一次 cur。
  • best 记录所有这些 cur 的最大值。

复杂度

  • 时间复杂度：O(n)，每个元素只扫描一次。
  • 额外空间：O(1)，只保存 cur 和 best。

常见错误

  • 把 dp[i] 定义成“前 i 个元素里的最大和”，然后又写 dp[i - 1] + nums[i]，状态含义不一致。
  • 初始化 cur = 0，会在全负数组里错误返回 0。
  • 只返回最后的 cur，会漏掉中途出现的最大值。
  • 把子序列和子数组混淆；本题必须连续。

小结

  • 一维 DP 先写清楚 dp[i] 的含义，再写转移。
  • 本题最稳定的状态是：dp[i] 表示必须以 i 结尾的最大连续和。
  • 转移来源只有两个：接上前一个最优结尾，或从当前位置重新开始。
  • Kadane 只是把 dp 表压成 cur + best 的空间优化版本。

参考与延伸

  • LeetCode 53：Maximum Subarray
  • LeetCode 70：Climbing Stairs
  • LeetCode 746：Min Cost Climbing Stairs
  • LeetCode 198：House Robber

Notes

  • 题意和示例来自当前仓库旧稿中的 LeetCode 53 摘要。
  • 代码语言按本仓库当前 LeetCode 教程默认选择 Python。