状态定义#

定义 $dp[i]$ 为以 $\text{nums}[i]$ 结尾的最大子数组和。注意这里的关键限制是”必须以 $\text{nums}[i]$ 结尾”——这让我们可以从子问题递推。

💡 DP 设计技巧：当问题问”任意区间的最优值”，常见的套路是强制状态以当前位置结尾，然后在所有 $dp[i]$ 中取最大值。这让我们获得了”前一个状态 + 当前元素”的递推关系。

对于位置 $i$，我们有两种选择：

• 自成一派：从 $\text{nums}[i]$ 开始一个全新的子数组，和为 $\text{nums}[i]$
• 延续前朝：把 $\text{nums}[i]$ 接到以 $\text{nums}[i-1]$ 结尾的最大子数组后面，和为 $dp[i-1] + \text{nums}[i]$

取两者中的较大值，得到状态转移方程：

$dp[i] = \max(\text{nums}[i],\ dp[i-1] + \text{nums}[i])$

最终答案就是 $\max\limits_{0 \le i < n} dp[i]$。

空间优化#

观察转移方程：$dp[i]$ 仅依赖于 $dp[i-1]$，我们不需要维护整个 dp 数组，只需一个变量 pre 记录 $dp[i-1]$ 即可。

同时注意到，$dp[i-1]$ 只有在 > 0 时才对 $dp[i]$ 有正向贡献——如果 $dp[i-1] \le 0$，那么 $\max(\text{nums}[i], dp[i-1] + \text{nums}[i]) = \text{nums}[i]$，等价于「丢弃之前的所有累加」。

因此代码可以简化为：

1
class Solution:
2
    def maxSubArray(self, nums: List[int]) -> int:
3
        ans = float('-inf')
4
        pre = 0
5

6
        for x in nums:
7
            pre = max(pre, 0) + x
8
            ans = max(ans, pre)
9

10
        return ans

关键一行 pre = max(pre, 0) + x 的语义：

• 如果 pre > 0，说明前面的累积对当前元素有正向贡献 → 累加上 x
• 如果 pre \le 0，说明前面的累积只会拖累当前元素 → 丢弃，从 x 重新开始

🧠 直觉理解：想象你是一个股民，每天都有盈亏。pre 就是你当前的累计收益，max(pre, 0) 就是在问自己——“我之前是赚了还是亏了？“亏了就清仓从头开始，赚了就继续持有。

这正是 Kadane 算法最优雅的写法——将 DP 状态转移与贪心决策融为一体。

执行过程追踪#

以 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例，追踪 pre 和 ans 的变化：

最终 ans = 6，对应子数组 [4, -1, 2, 1]。

可以观察到，pre 在位置 i=0, 1, 3 处 ≤ 0 时被”重置”——这恰好对应了”切断负数前缀，重新开始”的贪心决策。最终的最大值 6 出现在 i=6。