LeetCode 53：最大子数组和（Maximum Subarray）题解

Maximum Subarray 是 LeetCode Hot 100 里面一道非常经典的动态规划题。

这道题看起来不复杂，题意也非常直接： 给定一个整数数组，找出其中和最大的连续子数组，并返回这个最大和。

但它之所以经典，是因为它特别适合用来理解一个非常重要的动态规划思想：

当前位置的最优结果，往往只和前一个位置的最优结果有关。

很多人第一次接触这道题时，会先想到暴力枚举所有子数组，再逐个计算它们的和。这样当然可以做出来，但效率不够高。 而你给出的这份 Java 代码，使用的是这道题最经典、最简洁的一种写法，也就是：

Kadane 算法 / 动态规划优化写法

它的核心只有一句话：

当前子数组要么接在前面的最优后缀后面，要么从自己重新开始。

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给定一个整数数组 nums，请你找出一个具有最大和的 连续子数组，并返回其最大和。

注意这里有两个关键词：

1. 子数组必须连续

2. 只需要返回最大和，不要求返回具体子数组

例如：

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

这道题的答案是：

6

因为和最大的连续子数组是：

[4,-1,2,1]

它们的和为：

4 + (-1) + 2 + 1 = 6

这道题的关键就在于： 我们要找的是“连续”的一段，而不是随便挑几个数。

示例

示例 1

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

最大和来自连续子数组：

[4,-1,2,1]

示例 2

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

数组里只有一个元素，那最大子数组自然就是它自己。

示例 3

输入：nums = [5,4,-1,7,8]
输出：23

整个数组加起来就是最大和：

5 + 4 + (-1) + 7 + 8 = 23

最直接的想法是什么？

如果不考虑优化，一个最自然的思路就是：

• 枚举所有可能的连续子数组

• 计算每个子数组的和

• 取其中最大值

例如数组长度是 n：

• 子数组起点有 n 种选择

• 终点也有很多种选择

如果用两层循环枚举区间，再去算区间和，就可能做到：

O(n^2)

如果更暴力一点，每次再单独求和，那甚至会到：

O(n^3)

虽然能做出来，但题目显然还有更优解。

而这道题最经典的地方就在于，它其实可以在线性时间内解决：

O(n)

核心思路

这道题的关键在于思考：

以当前位置结尾的最大子数组和，应该怎么求？

假设我们定义：

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

那对于当前位置 i 来说，只有两种可能：

情况 1：把 nums[i] 接到前面的子数组后面

如果前面的“以 i-1 结尾的最大子数组和”是正数，那接上当前元素之后，和就会更大：

dp[i-1] + nums[i]

情况 2：从 nums[i] 自己重新开始

如果前面的和是负数，那接上去只会拖后腿，不如直接从当前元素重新开一个子数组：

nums[i]

所以状态转移方程就是：

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

这就是整道题最核心的公式。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    public int maxSubArray(int[] nums) {
        int maxPre = 0, res = nums[0];

        for (int num : nums) {
            // maxPre 表示“以当前元素结尾的最大子数组和”
            maxPre = Math.max(maxPre + num, num);

            // res 记录全局最大值
            res = Math.max(res, maxPre);
        }

        return res;
    }
}

代码拆解

这段代码非常短，但它其实已经把动态规划的核心思想压缩到了极致。 如果第一次看，可能会觉得有点抽象。下面一步一步来看。

1. maxPre 表示什么？

int maxPre = 0, res = nums[0];

这里的 maxPre 表示：

以当前元素结尾的最大子数组和

注意，它不是“到当前位置为止的全局最大值”，而是：

• 当前子数组必须以这个位置结尾

• 它是一个局部状态

例如遍历到某个位置 i 时，maxPre 表示的就是：

dp[i]

也就是“以 nums[i] 为结尾”的最优结果。

2. res 又表示什么？

res = nums[0];

res 表示的是：

遍历到当前为止，全局的最大子数组和

也就是说：

• maxPre 是局部最优

• res 是全局最优

这两个变量分工不同：

• maxPre 负责状态转移

• res 负责记录答案

3. 为什么状态转移是 max(maxPre + num, num)？

maxPre = Math.max(maxPre + num, num);

这是整道题最核心的一句。

假设当前遍历到的元素是 num，那么“以当前元素结尾的最大子数组和”只有两种来源：

第一种：接在前面的最大后缀后面

maxPre + num

也就是把当前元素接到前一个位置的最佳连续子数组后面。

第二种：从当前元素重新开始

num

如果前面的和是负数，那接上去只会让总和更小，所以不如重新开一个新的子数组。

因此当前状态取两者最大值：

max(maxPre + num, num)

这一步其实非常符合直觉：

前面的和如果有用，就接着用；前面的和如果没用，就扔掉重来。

4. 为什么每次都要更新 res？

res = Math.max(res, maxPre);

因为 maxPre 只是“当前结尾”的最优值， 但题目要的是整个数组范围内最大的那个连续子数组和。

所以每走到一个位置，都要拿当前的 maxPre 和历史最大值 res 比一下，看看能不能刷新答案。

这样遍历一遍数组后，res 就会保存全局最大子数组和。

手动模拟一遍

我们用最经典的样例来走一遍：

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

初始：

maxPre = 0
res = -2

第 1 个数：-2

maxPre = max(0 + (-2), -2) = -2
res = max(-2, -2) = -2

第 2 个数：1

maxPre = max(-2 + 1, 1) = 1
res = max(-2, 1) = 1

说明前面的和是负数，直接从 1 重新开始更好。

第 3 个数：-3

maxPre = max(1 + (-3), -3) = -2
res = max(1, -2) = 1

以 -3 结尾的最大和变成了 -2，但全局最大值还是 1。

第 4 个数：4

maxPre = max(-2 + 4, 4) = 4
res = max(1, 4) = 4

因为前面的 -2 没什么帮助，所以直接从 4 重新开始更优。

第 5 个数：-1

maxPre = max(4 + (-1), -1) = 3
res = max(4, 3) = 4

第 6 个数：2

maxPre = max(3 + 2, 2) = 5
res = max(4, 5) = 5

第 7 个数：1

maxPre = max(5 + 1, 1) = 6
res = max(5, 6) = 6

这时候得到最大值 6，对应子数组就是：

[4,-1,2,1]

后面继续遍历，最终 res 仍然保持为 6。

为什么这个方法是正确的？

因为对于每个位置 i，任何一个以 i 结尾的连续子数组，都只有两种构造方式：

1. 它只是当前元素自己

2. 它是在“以 i-1 结尾的某个连续子数组”后面再接上当前元素

而如果要让它最大，那前面的部分显然只需要保留“以 i-1 结尾的最大子数组和”即可。 这就说明状态转移完全成立：

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

再把所有 dp[i] 中的最大值取出来，就是全局答案。

所以这个算法本质上就是一个非常标准的动态规划过程，只不过我们把数组 dp 压缩成了一个变量 maxPre。

为什么 maxPre 初始值可以是 0？

很多人第一次看到这里会有一点疑惑：

int maxPre = 0

如果数组全是负数，不会出问题吗？

其实不会。 因为每一步真正的状态转移是：

maxPre = Math.max(maxPre + num, num);

也就是说，即使 maxPre 开始是 0，第一个元素也会立刻把状态修正到正确值。

例如：

nums = [-3]

那么：

maxPre = max(0 + (-3), -3) = -3

而 res 一开始就初始化成了 nums[0]，所以答案也不会被错误地变成 0。

这就是为什么这份代码在全负数数组下依然是正确的。

复杂度分析

时间复杂度

只遍历了一次数组，每个元素只处理一次，所以时间复杂度是：

O(n)

空间复杂度

只使用了两个额外变量：

• maxPre

• res

所以空间复杂度是：

O(1)

这也是这道题最经典写法的一个重要优点： 不仅时间复杂度低，而且空间复杂度也被压缩到了常数级。

这道题真正想考什么？

这道题表面上是在求“最大子数组和”，但本质上非常适合训练动态规划里最重要的一种思维方式：

第一，如何定义状态

如果你能想到：

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

那么后面的转移就会非常自然。

很多动态规划题的难点，其实都不在于公式本身，而在于“状态到底怎么定义”。

第二，如何把二维/全局问题转成局部决策

题目要求的是全局最大和，但我们并没有直接去维护所有子数组。 而是先求出每个位置的局部最优，然后再在这些局部最优里取全局最优。

这正是动态规划非常经典的一种思路。

第三，如何做状态压缩

原本我们可以开一个 dp[] 数组，但由于 dp[i] 只依赖 dp[i-1]，所以可以直接压缩成一个变量。

这也是动态规划优化里非常常见的技巧。

这道题为什么也叫 Kadane 算法？

这道题的这个线性解法，在很多资料里都叫：

Kadane 算法

它的核心思想其实就是你这份代码里体现的那样：

• 当前和如果有帮助，就继续累加

• 当前和如果变成负担，就从当前元素重新开始

这个思路非常简洁，也非常优雅，因此成为了最大子数组和问题的经典解法。

和前缀和有什么关系？

有些人第一次看到这题时，也可能会想到前缀和。

前缀和当然可以用来快速计算某一段区间和，但这题真正难的地方不是“怎么算某一段和”，而是：

怎么快速找到那一段最优区间。

而 Kadane 算法恰好直接绕过了枚举区间这件事，改成了在线维护“当前最优后缀和”，因此效率更高、思路也更简洁。

总结

这道题的核心思想可以概括成一句话：

对于每个位置，最大子数组和要么接在前一个位置的最优后缀后面，要么从当前元素自己重新开始。

具体做法就是：

1. 用 maxPre 表示“以当前元素结尾的最大子数组和”

2. 遍历数组时更新：

maxPre = max(maxPre + num, num)

3. 用 res 记录遍历过程中的全局最大值

4. 最终返回 res

这样就能在：

O(n)

的时间复杂度和：

O(1)

的空间复杂度下解决问题。

这是一道非常经典、也非常值得反复理解的动态规划题。 因为它会让你真正体会到：

• 状态定义有多重要

• 局部最优如何推出全局最优

• 动态规划并不一定需要大数组

• 很多时候一个变量就足够表达状态

把这道题真正吃透之后，再去看：

• 乘积最大子数组

• 打家劫舍

• 股票买卖系列

• 连续子数组类 DP 题目

你会明显更容易抓住核心。

因为“最大子数组和”本身就是动态规划入门里最经典的一道模板题。