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 <= nums.length <= 105
• -104 <= nums[i] <= 104

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

类似跳跃游戏

滑动窗口

1. 记录窗口和的最大值
2. 如果窗口和小于零，则重置窗口和和窗口。

class Solution {
    public int maxSubArray(int[] nums) {
        // 定义左指针
        int left = 0;
        // 定义右指针
        int right = 0;
        // 定义窗口中的元素和，初始化为0
        int sumOfWindow = 0;
        // 定义结果，初始化为最小值
        int res = Integer.MIN_VALUE;

        // 只要右指针没有到数组末尾，就一直往右走
        while (right < nums.length) {
            // 右指针往右走一步，加入当前元素到窗口和
            sumOfWindow += nums[right];
            // 更新结果，比较当前窗口的和与之前的最大值
            res = Math.max(res, sumOfWindow);
            // 移动右指针
            right++;
            
            // 如果当前窗口和小于0，说明它对后续的子数组没有贡献，重置窗口。重点。
            if (sumOfWindow < 0) {
                sumOfWindow = 0;
                // 左指针等于右指针，重置窗口
                left = right;
            }
        }
        
        return res;
    }
}

• 时间复杂度：O(n)，因为左右指针各遍历一次数组。
• 空间复杂度：O(1)，只使用了常数个变量。

动态规划，数组递推

dp[i] 表示以第 i 个元素结尾的子数组的最大和，dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])： 要么选择当前元素 nums[i]，要么选择当前元素加上前一个位置的最大和 dp[i - 1]。dp[] 数组中的最大值表示整个数组的最大子数组和。

class Solution {
    public int maxSubArray(int[] nums) {
        // 获取数组的长度
        int n = nums.length;
        // 定义 dp 数组，其中 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和
        int[] dp = new int[n];
        // 初始化 base case，dp[0] 就是第一个元素
        dp[0] = nums[0];
        
        // 状态转移，确定以每个位置结尾的子数组的最大和 dp[i]
        for (int i = 1; i < n; i++) {
            // dp[i] 的状态转移方程：
            // 要么选择当前元素 nums[i]，要么选择当前元素加上前一个位置的最大和 dp[i - 1]。重点。
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }

        // 从 dp[] 数组中找出最大值，表示整个数组的最大子数组和
        int res = Integer.MIN_VALUE;
        for (int j : dp) {
            res = Math.max(res, j);
        }

        return res;
    }
}

• 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历一次数组。
• 空间复杂度：O(n)，需要一个长度为 n 的 dp 数组。

贪心，滚动更新，最大前缀和。

正序计算以每个元素结尾的子数组的最大和。类似跳跃游戏

注意到动态规划解法中的 dp[i] 只依赖于 dp[i-1]，所以可以用一个变量 pre 来记录 dp[i-1] 的值，从而节省空间。

滚动更新本质上是贪心，用一个变量而不是一个数组记录历史信息。

public class Solution {

    public int maxSubArray(int[] nums) {
        // pre 表示以前一个位置结尾的子数组的最大和，初始值为 0
        int pre = 0;
        // res 用于记录最大子数组的和，初始值为数组的第一个元素
        int res = nums[0];
        
        // 遍历数组中的每一个元素
        for (int num : nums) {
            // 更新当前子数组的最大和，若 pre + num 小于 num，则从 num 开始新的子数组，等价于pre += Math.max(num, 0)
            pre = Math.max(pre + num, num);
            // 更新最大子数组的和
            res = Math.max(res, pre);
        }
        
        // 返回最大子数组的和
        return res;
    }
}

• 时间复杂度：O(n)，其中 n 是数组的长度。只需要遍历一次数组。
• 空间复杂度：O(1)，只使用了常数个变量。

原地修改数组：

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            // nums[i]加上前面的最大前缀和
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

贪心，最小前缀和

连续子数组的和，实际上是两个「前缀和」相减。遍历数组，每次循环更新当前前缀和和最小前缀和， 当前子数组的最大和即当前前缀和减去之前的最小前缀和（即遍历到目前为止的最小前缀和 min）。

class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化答案为数组的第一个元素
        int ans = nums[0];
        // 初始化最小前缀和为0（相当于假设一个初始最小前缀和为0）
        int min = 0;
        // 初始化当前的前缀和为0
        int sum = 0;
        
        // 遍历数组中的每一个元素
        for (int num : nums) {
            // 累加当前元素到前缀和
            sum += num;
            // 计算当前子数组的最大和。使用当前的前缀和 sum 减去遍历到目前为止的最小前缀和 min。重点。
            ans = Math.max(ans, sum - min);
            // 更新最小前缀和。将 min 更新为遍历到当前元素时的最小前缀和，以便在接下来的迭代中使用。
            min = Math.min(min, sum);
        }
        
        // 返回最大子数组的和
        return ans;
    }
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)