# 53. 最大子数组和

力扣题目链接 (opens new window)

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

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

输出：6

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

示例 2：

输入：nums = [1]

输出：1

示例 3：

输入：nums = [-1]

输出：-1

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

# 思路

# 暴力解法

最直观的思路：枚举所有连续子数组，计算每个子数组的和，取最大值。

第一层 for 循环设置起始位置，第二层 for 循环从起始位置开始遍历，累加求和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) { // 设置起始位置
            count = 0;
            for (int j = i; j < nums.size(); j++) { // 从起始位置i开始遍历寻找最大值
                count += nums[j];
                result = count > result ? count : result;
            }
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n^2)
空间复杂度：O(1)

O(n^2) 的复杂度，在数据量 10^5 的量级下会超时。能不能优化？

# 贪心解法

暴力解法的问题在于：大量重复计算。比如子数组 [0,1,2] 和 [0,1,2,3]，[0,1,2] 的和在第二次计算时又算了一遍。

那能不能一遍遍历就搞定？

贪心贪的是哪里呢？

如果 -2 和 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前"连续和"为负数的时候立刻放弃，从下一个元素重新计算"连续和"，因为负数加上下一个元素 "连续和"只会越来越小。

全局最优：选取最大"连续和"。

局部最优的情况下，并记录最大的"连续和"，可以推出全局最优。

从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i] 变为负数，那么就应该从 nums[i+1] 开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

那有录友问了，区间终止位置不用调整么？如何才能得到最大"连续和"呢？

区间的终止位置，其实就是如果 count 取到最大值了，及时记录下来：

if (count > result) result = count;

这样相当于是用 result 记录最大子序和区间和（变相的算是调整了终止位置）。

让我们用示例 nums = [-2,1,-3,4,-1,2,1,-5,4] 逐步模拟一遍：

如图所示，整个过程的关键就两步：

累加：count 加上当前元素
判断：如果 count 为负，重置为 0（相当于移动起始位置）；如果 count 比 result 大，更新 result（相当于移动终止位置）

那么不难写出如下 C++ 代码（关键地方已经注释）：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n)
空间复杂度：O(1)

# 常见误区

误区一：全是负数时结果是 0？

不少录友认为如果输入用例都是 -1，或者都是负数，贪心算法跑出来的结果是 0。这是又一次证明脑洞模拟不靠谱的经典案例，建议大家把代码运行一下就知道了，也会理解为什么 result 要初始化为最小负数。

误区二：遇到负数就重置？

很多录友分不清：是遇到负数就选择重置起始位置，还是连续和为负才重置？

在模拟过程中可以发现，4 遇到 -1 的时候，我们依然累加了，为什么呢？

因为和为 3，只要连续和还是正数就会对后面的元素起到增大总和的作用。所以只要连续和为正数我们就保留。

那 4 + (-1) 之后不就变小了吗？会不会错过 4 成为最大连续和的可能性？

并不会，因为 result 一直在更新最大的连续和，4 已经被记录过了。后面连续和变成 3，也不会对最后结果有影响。

# 动态规划

贪心的思路不太好想，我们换一个角度——动态规划。

这道题的动态规划解法其实非常直接，甚至比贪心更好理解。

动规五部曲如下：

1. 确定 dp 数组以及下标的含义

dp[i]：以 nums[i] 为结尾的最大连续子数组和为 dp[i]。

注意，是"以 nums[i] 为结尾"，不是"从 0 到 i"。这个定义非常关键，它保证了子数组的连续性。

2. 确定递推公式

dp[i] 只有两个方向可以推出来：

dp[i - 1] + nums[i]：把 nums[i] 加入前面的连续子数组
nums[i]：从 nums[i] 重新开始一段新的连续子数组

为什么会有第二种选择？因为如果 dp[i-1] 是负数，它只会拖累 nums[i]，不如从 i 重新开始。

取最大的，所以递推公式为：

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

3. dp 数组如何初始化

从递推公式可以看出 dp[i] 依赖于 dp[i-1]，dp[0] 是递推的基础。

根据 dp[i] 的定义，以 nums[0] 为结尾的最大连续子数组和就是 nums[0] 本身：

dp[0] = nums[0]

4. 确定遍历顺序

dp[i] 依赖于 dp[i-1]，需要从前向后遍历。

5. 举例推导 dp 数组

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例，推导 dp 数组如下：

从表中可以看出：

i=0: dp[0] = -2（只有 nums[0] 自己）
i=1: dp[1] = max(-2+1, 1) = 1，前面是负数拖累了，从头开始更好
i=2: dp[2] = max(1+(-3), -3) = -2，延续了前面的，但变负了
i=3: dp[3] = max(-2+4, 4) = 4，前面是负数拖累了，从头开始更好
i=4: dp[4] = max(4+(-1), -1) = 3，前面是正数有贡献，接着累加
i=5: dp[5] = max(3+2, 2) = 5
i=6: dp[6] = max(5+1, 1) = 6 ✅ 最大值！
i=7: dp[7] = max(6+(-5), -5) = 1，-5 把前面的成果吃掉了一些
i=8: dp[8] = max(1+4, 4) = 5

注意：最后的结果不是 dp[n-1]，而是整个 dp 数组中的最大值！ 因为最大子数组不一定以最后一个元素结尾。

所以在递推的过程中，用一个变量 result 记录 dp[i] 的最大值即可。

完整代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n)
空间复杂度：O(n)

# 空间优化

注意到 dp[i] 只依赖于 dp[i-1]，不需要整个 dp 数组，用一个变量就够了：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = nums[0];
        int dp = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp = max(dp + nums[i], nums[i]);
            result = max(result, dp);
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：O(n)
空间复杂度：O(1)

空间优化后的动规代码，和贪心代码是不是很像？贪心和动规本质上是同一个思路的不同表达：

贪心角度：连续和为负就重置 → 等价于 dp[i-1] < 0 时选择 nums[i]
动规角度：dp[i] = max(dp[i-1] + nums[i], nums[i]) → 连续和为负时自然会选择重新开始

# 总结

这道题从暴力到贪心到动规，是一个经典的优化过程：

方法	时间复杂度	空间复杂度	核心思想
暴力	O(n^2)	O(1)	枚举所有子数组
贪心	O(n)	O(1)	连续和为负就重置
动规	O(n)	O(n)/O(1)	dp[i] = max(dp[i-1]+nums[i], nums[i])

贪心和动规殊途同归，本质都是在做一件事：前面的连续和如果是负数，就抛弃它，从当前元素重新开始。

这道题的动规解法也叫 Kadane 算法，是最大子数组问题的经典解法。

# 其他语言版本

# Java

贪心：

class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            result = Math.max(result, count); // 取区间累计的最大值
            if (count <= 0) {
                count = 0; // 重置起始位置
            }
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划：

class Solution {
    public int maxSubArray(int[] nums) {
        int result = nums[0];
        int dp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp = Math.max(dp + nums[i], nums[i]);
            result = Math.max(result, dp);
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# Python

贪心：

class Solution:
    def maxSubArray(self, nums):
        result = float('-inf')
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > result:
                result = count
            if count <= 0:
                count = 0
        return result

1
2
3
4
5
6
7
8
9
10
11

动态规划：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = nums[0]
        dp = nums[0]
        for i in range(1, len(nums)):
            dp = max(dp + nums[i], nums[i])
            result = max(result, dp)
        return result

1
2
3
4
5
6
7
8

# Go

贪心：

func maxSubArray(nums []int) int {
    max := nums[0]
    count := 0
    for i := 0; i < len(nums); i++ {
        count += nums[i]
        if count > max {
            max = count
        }
        if count < 0 {
            count = 0
        }
    }
    return max
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划：

func maxSubArray(nums []int) int {
    result := nums[0]
    dp := nums[0]
    for i := 1; i < len(nums); i++ {
        dp = max(dp + nums[i], nums[i])
        result = max(result, dp)
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# JavaScript

贪心：

var maxSubArray = function(nums) {
    let result = -Infinity;
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        count += nums[i];
        if (count > result) result = count;
        if (count < 0) count = 0;
    }
    return result;
};

1
2
3
4
5
6
7
8
9
10

动态规划：

var maxSubArray = function(nums) {
    let result = nums[0];
    let dp = nums[0];
    for (let i = 1; i < nums.length; i++) {
        dp = Math.max(dp + nums[i], nums[i]);
        result = Math.max(result, dp);
    }
    return result;
};

1
2
3
4
5
6
7
8
9

# TypeScript

动态规划：

function maxSubArray(nums: number[]): number {
    let result = nums[0];
    let dp = nums[0];
    for (let i = 1; i < nums.length; i++) {
        dp = Math.max(dp + nums[i], nums[i]);
        result = Math.max(result, dp);
    }
    return result;
}

1
2
3
4
5
6
7
8
9

# Rust

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut result = nums[0];
        let mut dp = nums[0];
        for i in 1..nums.len() {
            dp = (dp + nums[i]).max(nums[i]);
            result = result.max(dp);
        }
        result
    }
}

1
2
3
4
5
6
7
8
9
10
11

# C

动态规划：

int maxSubArray(int* nums, int numsSize) {
    int result = nums[0];
    int dp = nums[0];
    for (int i = 1; i < numsSize; i++) {
        dp = (dp + nums[i]) > nums[i] ? (dp + nums[i]) : nums[i];
        result = result > dp ? result : dp;
    }
    return result;
}

1
2
3
4
5
6
7
8
9

验证登录状态...

# 53. 最大子数组和

# 思路

# 暴力解法

# 贪心解法

# 常见误区

# 动态规划

# 空间优化

# 总结

# 其他语言版本

# Java

# Python

# Go

# JavaScript

# TypeScript

# Rust

# C

评论