53. 最大子数组和#

生活中的算法#

想象你是一位股票交易员，手上有一支股票的每日涨跌数据。你想找出哪段连续的交易日能获得最大的收益。如果某天股票上涨5元，我们记为+5，下跌3元记为-3。找出总和最大的一段连续交易日，就是在寻找最大子数组和。

这个问题在现实生活中很常见。比如分析用户活跃度的波动趋势，研究气温变化的最大累积效应，或是评估企业连续几个月的盈利表现。

问题描述#

题目目标#

LeetCode第53题”最大子数组和”是这样描述的：给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1#

输入： nums = [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 说明： 连续子数组 [4,-1,2,1] 的和最大，为 6。

最直观的解法：暴力枚举#

最容易想到的方法是：枚举所有可能的子数组，计算它们的和，找出最大值。

让我们用一个简单的例子来理解：

nums = [1,-2,3,-1]
检查子数组 [1]：和为1
检查子数组 [1,-2]：和为-1
检查子数组 [1,-2,3]：和为2
检查子数组 [1,-2,3,-1]：和为1
检查子数组 [-2]：和为-2
...依此类推
找到最大和为3，对应子数组[3]

plaintext

优化解法：动态规划#

仔细思考会发现，我们在计算每个位置结尾的最大子数组和时，只需要关注前一个位置的最大子数组和是否值得接续。类似继承资产，如果之前继承的是正资产，不管多还是少，有总比没有好。我在之前的资产基础上，加上我目前的资产或者负债。可要是之前继承的是一笔负债，那我宁可不要，选择白手起家。

动态规划的原理#

定义dp[i]为以第i个数结尾的最大子数组和
如果前面的和是正数，就值得接续；如果是负数，就重新开始
状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])
最终答案是dp数组中的最大值

算法步骤演示#

用nums = [1,-2,3,-1]演示这个过程：

1. 处理1：
dp[0] = 1
当前最大和 = 1

2. 处理-2：
dp[1] = max(1-2, -2) = -1
当前最大和 = 1

3. 处理3：
dp[2] = max(-1+3, 3) = 3
当前最大和 = 3

4. 处理-1：
dp[3] = max(3-1, -1) = 2
最终最大和 = 3

plaintext

Java代码实现#

public int maxSubArray(int[] nums) {
    // 边界条件：如果数组为 null 或长度为 0，按题解约定直接返回 0
    if (nums == null || nums.length == 0) {
        // 空数组没有可选子数组
        return 0;
    }

    // 定义 dp 数组：dp[i] 表示“必须以下标 i 结尾”的最大子数组和
    int[] dp = new int[nums.length];
    // 初始化第 0 个位置：只能选择 nums[0] 自身
    dp[0] = nums[0];
    // 记录全局最大子数组和，初始值就是 dp[0]
    int maxSum = dp[0];

    // 从下标 1 开始遍历，逐步计算每个位置结尾的最优解
    for (int i = 1; i < nums.length; i++) {
        // 状态转移：
        // 1) 把 nums[i] 接在前一个最优子数组后面：dp[i-1] + nums[i]
        // 2) 从 nums[i] 重新开始一个新子数组：nums[i]
        // 取两者较大值作为 dp[i]
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        // 用当前位置的最优值更新全局答案
        maxSum = Math.max(maxSum, dp[i]);
    }

    // 返回整段数组中出现过的最大子数组和
    return maxSum;
}

java

进一步优化：空间优化#

观察发现，我们其实只需要前一个状态的值，不需要保存整个dp数组。

public int maxSubArray(int[] nums) {
    // 边界条件：空数组或 null，按题解约定返回 0
    if (nums == null || nums.length == 0) {
        // 没有元素时不存在有效子数组
        return 0;
    }

    // currentMax 表示“以当前下标结尾”的最大子数组和（滚动变量）
    int currentMax = nums[0];
    // maxSum 表示遍历到当前为止的全局最大子数组和
    int maxSum = nums[0];

    // 从第二个元素开始遍历，持续更新局部最优与全局最优
    for (int i = 1; i < nums.length; i++) {
        // 当前元素可选择：
        // - 接在前一段后面（currentMax + nums[i]）
        // - 自成一段（nums[i]）
        // 取较大者作为新的“以 i 结尾的最大和”
        currentMax = Math.max(currentMax + nums[i], nums[i]);
        // 更新全局最大值
        maxSum = Math.max(maxSum, currentMax);
    }

    // 返回最终答案
    return maxSum;
}

java

使用最小前缀#

class Solution {
    public int maxSubArray(int[] nums) {
        // pre 表示前缀和：pre = nums[0] + nums[1] + ... + nums[i]
        int pre = 0;
        // minPre 表示“当前下标之前出现过的最小前缀和”
        // 初始为 0，等价于允许子数组从下标 0 开始
        int minPre = 0;
        // maxSum 记录最大子数组和，初始化为最小整数，确保任何真实和都能更新它
        int maxSum = Integer.MIN_VALUE;
        // 逐个遍历数组元素，在线计算答案
        for(int i = 0; i < nums.length; i++){
            // 更新到当前位置 i 的前缀和
            pre += nums[i];
            // 以 i 结尾的最大子数组和 = 当前前缀和 - 之前最小前缀和
            // 用它尝试刷新全局最大值
            maxSum = Math.max(pre - minPre, maxSum);
            // 更新历史最小前缀和，供后续位置使用
            minPre = Math.min(minPre, pre);
        }
        // 返回最大子数组和
        return maxSum;
    }
}

java

解法比较#

让我们比较这些解法：

暴力枚举：

时间复杂度：O(n²)
空间复杂度：O(1)
优点：直观易懂
缺点：效率较低

动态规划：

时间复杂度：O(n)
空间复杂度：O(n)
优点：高效且易于理解
缺点：需要额外空间

空间优化版：

时间复杂度：O(n)
空间复杂度：O(1)
优点：时空效率都很高
缺点：代码不如dp数组版直观

扩展思考#

这道题目启发我们：

当遇到”最大”/“最小”类型的问题时，考虑动态规划
寻找问题中的递推关系
关注是否可以优化空间复杂度
注意处理负数的情况

类似的问题还有：

买卖股票的最佳时机
乘积最大子数组
环形子数组的最大和

小结#

通过最大子数组和这道题，我们不仅学会了一个经典的动态规划问题的解法，更重要的是理解了如何将复杂问题分解为子问题，并利用子问题的解构建最终答案。这种思维方式在解决其他动态规划问题时也会很有帮助。

记住，当遇到需要求解”最大连续和”类型的问题时，动态规划往往能提供一个优雅而高效的解决方案！