53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:
Input: nums = [1]
Output: 1

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

最大子数组。

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是动态规划，我参考了这个帖子，写的非常好，解释了 DP 的定义是怎么来的。设 dp[i] 是以 nums[i] 结尾的子数组的和。扫描数组，当遇到某个数 nums[i] 的时候，需要判断 dp[i - 1] 是否小于 0。如果小于 0，nums[i] + dp[i - 1] 的结果只会拖累当前的 dp[i]；如果大于 0，可以将 dp[i] = dp[i - 1] + nums[i] 。最后返回过程中找到的最大的 dp[i] 即可。

复杂度

时间O(n)
空间O(n)

代码

Java实现

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

优化

这种 DP 的思路也有节省空间的做法，其实我们并不一定需要知道每个 dp[i] 值的大小，我们只需要在遍历过程中记录一下最大的 dp 值即可。思路也是很类似，如果之前的值 prev 小于 0，一定会拖累 cur 的，所以 cur = nums[i]；反之如果 prev 大于 0，cur就变为 nums[i] + prev。每次用 res 记录一下当前的子数组的最大值之后，就可以把 cur 赋给 prev 以达到节省空间的目的了。

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int maxSubArray(int[] nums) {
        int prev = nums[0];
        int cur = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (prev < 0) {
                cur = nums[i];
            } else {
                cur = prev + nums[i];
            }
            res = Math.max(res, cur);
            prev = cur;
        }
        return res;
    }
}

优化二

还有另外一种思路，类似 DP 的做法，是去求局部最大和整体最大。设两个变量 sum 和 res，sum 记录当遍历到 nums[i] 的时候，sum + nums[i] 是否对值的扩大有帮助；res 记录最大的 sum 值。

时间O(n)
空间O(1)

代码

Java实现

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

相关题目

53. Maximum Subarray
152. Maximum Product Subarray
918. Maximum Sum Circular Subarray
978. Longest Turbulent Subarray
1186. Maximum Subarray Sum with One Deletion
2272. Substring With Largest Variance