53. 最大子数组和

鲁迅曾说，日子总要一天天的过，就过成了一生。每天都要有所收获，每天都要

有所进步，这样子，我们的生活才会更加充实，更加有意义。今天，我们就来学

习一道算法题——最大子数组合，希望你能够有所收获。

题意

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个

元素），返回其最大和。

子数组 是数组中的一个连续部分。

难度

中等

示例

示例 1：

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

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]

输出：1

示例 3：

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

输出：23

分析 1

遇到这种题目，暴力算法是最容易想到的，直接穷举所有可能的子数组，计算每个子数组

的和，找到最大值。

class Solution {

public int maxSubArray(int[] nums) {

int n = nums.length;

int maxSum = Integer.MIN_VALUE; // 初始化为最小值

// 枚举每一个子数组

for (int i = 0; i < n; i++) {

int currentSum = 0; // 当前子数组的和

for (int j = i; j < n; j++) {

currentSum += nums[j]; // 累加当前子数组的元素

 maxSum = Math.max(maxSum, currentSum); // 更新最大和

}

}

return maxSum; // 返回最大子数组的和

}

public static void main(String[] args) {

Solution solution = new Solution();

int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

System.out.println(solution.maxSubArray(nums)); // 输出: 6

}

}

算法非常简单，两层 for 循环，第一层从 i 到 n，第二层就是从 i+1 到 n，这样子就能够枚

举出所有的子数组，然后计算每个子数组的和，找到最大值。

只不过效率会比较低，会超出时间限制。

053.最大子数组和-20241116111756.png

分析 2

暴力算法的问题在于，我们重复计算了很多子数组的和，比如说，我们在计算 [0,1,2] 和

的时候，已经计算了 [0,1] 的和，而在计算 [0,1,2,3] 和的时候，又计算了 [0,1,2] 的和，

这样子就会有很多重复的计算，所以效率低。

那接下来，我们的目标就是减少重复的计算。

那针对最值问题，动态规划 就非常适合。动态规划的关键是通过历史信息推导出当前的

最优解，即用一个状态记录以当前位置为结尾的子数组的最大和，并用这个信息帮助我们

推导下一步。

比如说，我们定义 dp[i] 表示以 nums[i] 结尾的最大子数组和，那么我们可以得到这样一

个状态转移方程：

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

这个方程的意思是，要么是当前元素加上前面的最大子数组和，要么就是当前元素自己作

为一个子数组。

如果 dp[i-1] > 0，说明当前子数组的前缀和是正数，有助于增加 dp[i] 的最大值，因此：

dp[i] = dp[i - 1] + nums[i]

如果 dp[i-1] <= 0，说明当前子数组的前缀和是负数，对增加 dp[i] 的最大值没有帮助，

因此：

dp[i] = nums[i]

初始状态是 dp[0] = nums[0]，也就是第一个数构成第一个子数组的和。

好，接下来我们来看一下代码实现：

class Solution {

public int maxSubArray(int[] nums) {

int n = nums.length;

int[] dp = new int[n]; // 定义 dp 数组

dp[0] = nums[0]; // 初始化第一个状态

int maxSum = dp[0]; // 初始化全局最大值

// 从第二个元素开始遍历

for (int i = 1; i < n; i++) {

// 状态转移方程

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

// 更新全局最大值

maxSum = Math.max(maxSum, dp[i]);

}

return maxSum; // 返回最大子数组的和

}

public static void main(String[] args) {

Solution solution = new Solution();

int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

System.out.println(solution.maxSubArray(nums)); // 输出: 6

}

}

非常好理解，代码也很简单，关键就是定义状态、以及状态转移方程和初始状态，然后就

是遍历数组，更新状态，最后返回最大值。

来看一下题解效率：

053.最大子数组和-20241116120557.png

还不错哦。

分析 3

从动态规划的解法里，我们可以注意到，两个关键点：

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

// 更新全局最大值

maxSum = Math.max(maxSum, dp[i]);

dp[i] 和 dp[i-1] 有关，所以我们可以用一个变量 maxPre 来记录 dp[i-1]，这样子代码就

更简洁了。

class Solution {

public int maxSubArray(int[] nums) {

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

for (int num : nums) {

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

res = Math.max(maxPre, res);

}

return res;

}

}

• 通过变量 maxPre，省去传统动态规划解法中的 dp 数组，仅用一个变量记录以当前

元素为结尾的最大子数组和。

• 将状态转移方程和更新全局最大值放在 for-each 循环中，代码更加简洁。

时间复杂度：$ O(n) $，因为我们仅仅是对 nums 遍历了一遍。

053.最大子数组和-20241116121254.png

总结

我们在学习 LeetCode 的时候，千万不要忽视暴力算法的魅力，因为它可以让我们更好的

理解问题的本质，然后在此基础上去优化思路。

当然了，我们也可以总结一些套路，比如说这种最值问题，直接套动态规划，然后再去优

化，这样子就能够更快的解决问题。

力扣链接：https://leetcode.cn/problems/maximum-subarray/