Hot 100 --- 最大子数组和

本文概览：本文以LeetCode经典题目"最大子数组和"为例，从暴力解法入手，利用前缀和优化到维护最小前缀和的 O(n) 解法，再从动态规划角度重新理解，系统讲解如何利用"前数组和是否对当前元素有贡献"这一关键判断，将时间复杂度从 O(n²) 优化到 O(n)

一、题目

最大子数组和题目

二、题目分析

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

目标：找到和最大的连续子数组，返回其最大和

核心问题：如何决定一个子数组应该继续扩展还是重新开始

思路概览

Java实现代码如下

public int maxSubArray(int[] nums) {
    // 当前元素的前的数组和
    int preNums = nums[0];
    // 全局最大的数
    int max = nums[0];

    for (int i = 1; i < nums.length; i++) {
        // 如果此时前数组和小于0，则说明前数组和对当前元素没有贡献，应该舍弃前数组和
        if (preNums < 0)
            preNums = nums[i];
        else
            // 否则说明前数组和对当前元素有贡献，应该保留前数组和
            preNums += nums[i];
        // 更新全局最大数
        max = Math.max(max, preNums);
    }
    return max;
}

思路简要说明

前数组和：preNums 记录以当前位置结尾的子数组的最大和。它代表的是"如果选择以当前元素结尾，前面能接上的最大子数组和是多少"
贡献判断：如果前数组和小于 0，说明它对当前元素是负贡献——接上它只会让和变小，应该舍弃前数组和，从当前元素重新开始；如果前数组和大于等于 0，说明它对当前元素是正贡献或零贡献，接上它不会让和变小，应该保留前数组和
全局最大值：每次更新 preNums 后，与全局最大值 max 比较，保留更大的那个。因为最大子数组不一定以最后一个元素结尾，所以需要在每一步都记录全局最优

三、思路详解

暴力解法入手

最自然的想法是：枚举所有可能的子数组，计算每个子数组的和，取最大值

具体来说，用双重循环枚举子数组的起点和终点，对每个子数组求和并更新最大值

显然可以得出以下结论

时间复杂度：O(n²)，枚举所有子数组起点和终点
核心瓶颈：大量重复计算，每次确定新的起点后都要重新累加求和
关键思考：能否利用前一次计算的结果，避免重复求和？

前缀和优化

暴力解法中每次确定新起点后都要重新累加，存在大量重复计算。利用前缀和可以避免重复累加：子数组 nums[j..i] 的和 = pre[i] - pre[j-1]，其中 pre[i] 表示 nums[0] 到 nums[i] 的累加和

但问题来了：对于每个终点 i，我们要找使得 pre[i] - pre[j-1] 最大的起点 j，也就是要找 i 之前最小的 pre[j-1]。如果对每个终点都枚举所有起点，相当于枚举了全部子数组，和暴力解法没有本质区别

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] pre = new int[n];
    pre[0] = nums[0];
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + nums[i];
    }

    int max = nums[0];
    // 枚举终点i，枚举起点j，相当于枚举全部子数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int sum = pre[i] - (j > 0 ? pre[j - 1] : 0);
            max = Math.max(max, sum);
        }
    }
    return max;
}

时间复杂度：O(n²)，虽然避免了重复累加，但仍然要枚举所有子数组的起点和终点
核心瓶颈：对每个终点都枚举了所有小于它的起点，本质上还是枚举了全部子数组
关键思考：前缀和还能更优化吗？对于每个终点 i，我们只需要 i 之前最小的前缀和，那能不能在遍历过程中动态维护这个最小值，而不是每次都重新枚举？

前缀和 + 维护最小前缀和

既然对于终点 i，最大子数组和 = pre[i] - min(pre[0..i-1])，那我们可以在遍历时动态维护遍历到当前位置之前的最小前缀和，这样每个终点只需要 O(1) 就能得到以它结尾的最大子数组和

思路详解

回顾前缀和的公式：子数组 nums[j..i] 的和 = pre[i] - pre[j-1]。对于固定的终点 i，pre[i] 是确定的，要让子数组和最大，就需要 pre[j-1] 尽可能小

也就是说，我们不需要枚举所有起点 j，只需要知道 i 之前最小的前缀和是多少就够了

那这个最小前缀和怎么得到？我们可以在遍历数组的同时，用一个变量 minPreSum 记录遍历到当前位置之前的最小前缀和。每到一个新位置，先用 preSum - minPreSum 计算以当前位置结尾的最大子数组和，然后更新 minPreSum

为什么 minPreSum 初始化为 0？

因为前缀和数组有一个隐含的 pre[-1] = 0（即没有任何元素时的前缀和为 0）。当子数组从索引 0 开始时，nums[0..i] 的和 = pre[i] - pre[-1] = pre[i] - 0。所以 minPreSum 初始为 0，可以正确处理子数组从开头开始的情况

举例说明

以 nums = [-2, 1, -3, 4] 为例

i	nums[i]	preSum	minPreSum	preSum - minPreSum	max
0	-2	-2	0	-2 - 0 = -2	-2
1	1	-1	-2	-1 - (-2) = 1	1
2	-3	-4	-2	-4 - (-2) = -2	1
3	4	0	-4	0 - (-4) = 4	4

注意每一步的顺序：先计算 preSum - minPreSum，再更新 minPreSum。这保证了 minPreSum 始终是当前位置之前的最小前缀和，不会把当前前缀和也算进去

public int maxSubArray(int[] nums) {
    int max = nums[0];
    int preSum = 0;       // 当前前缀和
    int minPreSum = 0;    // 遍历到当前位置之前的最小前缀和

    for (int num : nums) {
        preSum += num;
        // 当前前缀和 - 之前最小的前缀和 = 以当前位置结尾的最大子数组和
        max = Math.max(max, preSum - minPreSum);
        // 更新最小前缀和
        minPreSum = Math.min(minPreSum, preSum);
    }
    return max;
}

时间复杂度：O(n)，只需遍历一次
空间复杂度：O(1)

这个解法已经是最优的了。但它的思路是从"前缀和之差"的角度出发，我们再换一个角度来理解这个问题，也就是动态规划

动态规划解法

思路分析

前缀和 + 维护最小前缀和的解法，核心是：对于每个位置，用当前前缀和减去之前最小的前缀和，得到以当前位置结尾的最大子数组和

我们换一个角度思考：不维护最小前缀和，而是直接维护以当前位置结尾的最大子数组和

定义 dp[i] 为以 nums[i] 结尾的最大子数组和，那么：

如果 dp[i-1] > 0，说明前面的子数组和是正贡献，接上它会让和更大，所以 dp[i] = dp[i-1] + nums[i]
如果 dp[i-1] ≤ 0，说明前面的子数组和是零贡献或负贡献，接上它只会让和变小或不变，不如从 nums[i] 重新开始，所以 dp[i] = nums[i]

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

最终答案就是所有 dp[i] 中的最大值

两种解法的关系

前缀和 + 维护最小前缀和的解法，计算的是 pre[i] - min(pre[0..i-1])，即"当前前缀和减去之前最小的前缀和"

动态规划解法，计算的是"以当前位置结尾的最大子数组和"，如果前数组和为正就接上，为负就舍弃

两者本质上是等价的：前数组和 dp[i-1] 就等于 pre[i-1] - min(pre[0..i-2])。当 dp[i-1] < 0 时，说明 pre[i-1] < min(pre[0..i-2])，此时 pre[i-1] 本身就是新的最小前缀和，应该从当前元素重新开始；当 dp[i-1] ≥ 0 时，说明 pre[i-1] ≥ min(pre[0..i-2])，应该接上前面的子数组

为什么"前数组和小于0就舍弃"是正确的？

这是整个算法的核心。我们用一个具体的例子来理解

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

遍历到 nums[3] = 4 时，前面已经算出以 nums[2] 结尾的最大子数组和是 -2

现在要决定：以 4 结尾的最大子数组，要不要把前面的 -2 接上？

接上：-2 + 4 = 2
不接：4

显然不接更好。原因很简单：前面的和是负数，接上只会拖后腿

这个逻辑对任何位置都成立：如果前面的子数组和是负数，它对当前元素就是负贡献，无论当前元素多大或多小，都不应该接上

空间优化

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

举例说明

以 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例

i	nums[i]	preNums（前）	前数组和<0?	preNums（后）	max
0	-2	-	-	-2	-2
1	1	-2	是，舍弃	1	1
2	-3	1	否，保留	1+(-3)=-2	1
3	4	-2	是，舍弃	4	4
4	-1	4	否，保留	4+(-1)=3	4
5	2	3	否，保留	3+2=5	5
6	1	5	否，保留	5+1=6	6
7	-5	6	否，保留	6+(-5)=1	6
8	4	1	否，保留	1+4=5	6