【LC100】No53. 最大子数组和

题目描述

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

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

提示:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

进阶：

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

示例

示例 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

链接

思路

以前我真做出来过！

解法一：前缀和

经历过前几天数组题的毒打，看到“子数组和”现在可以“有端联想”到——前缀和的差值。

本来是想计算出所有前缀和，然后找到最大值和最小值，最后差值就是最大子数组和的。但是发现这样做无法保证前缀和最小值在最大值的左边出现。

由此，可以继续考虑，我们要保证前缀和的计算顺序，那么可以无需先计算出前缀和数组，在循环中不断计算即可。

此时，只需要维护一个前缀和的最小值 min，一个最大差值 res。

在循环中计算完当前前缀和之后，再计算一下当前前缀和和最小前缀和的差值，如果比之前保存的 res 大则更新 res，之后和前缀和最小值 min 比较，小则更新 min。

代码

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int sum = 0;
        int min = 0, res = Integer.MIN_VALUE;
        for (int num : nums) {
            sum += num;
            res = Math.max(sum - min, res);
            min = Math.min(sum, min);
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

解法二：动态规划

本题符合动态规划的核心特征：

• 重叠子问题：当计算以 nums[i] 结尾的最大子数组和时，需要用到前面的 nums[i-1] 的最大子数组和。

• 最优子结构：最终所求的最大子数组和，可以拆分为分别以每个元素做结尾的子数组和的最大值。

• 无后效性：计算以 nums[i] 结尾的最大子数组和时，只需要用到 nums[i] 和前一个子问题以 nums[i-1] 结尾的最大子数组和，但不需要知道它是如何得到的。

因此我们可以用动态规划来解题。

状态定义：我们定义 f[i] = 以 nums[i] 结尾的子数组和的最大值

当 f[i - 1] < 0 时，计算 f[i] 时要保证最大，则不需要用 nums[i] 加 f[i-1]，只取 nums[i] 即可。

状态转移方程：f[i] = max(f[i - 1], 0) + nums[i]

初始条件：f[0] = nums[0]

最终解：所有 f 的最大值

计算 f[i] 时，只会用到 f[i - 1]，而不会用到更早的值，所以我们可以用滚动变量优化数组。

代码

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

// 优化为使用滚动变量来保存f
class Solution {
    public int maxSubArray(int[] nums) {
        int f = 0;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            f = Math.max(f, 0) + nums[i];
            res = Math.max(res, f);
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)