LeetCode.053.Maximum Subarray 最大连续子序列和

题目描述

53 Maximum Subarray
https://leetcode-cn.com/problems/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.

Example:

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

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.

---

相似题目

58同城基础架构部中间件，一面面试题

LeetCode.053.Maximum Subarray 最大连续子序列和
LeetCode.152.Maximum Product Subarray 最大连续子序列积

---

解题过程

设 dp[n] 是以 a[n] 为结尾的(必须包含a[n]在内)连续子序列的最大和，则有递推公式：
dp[n] = dp[n-1] + nums[n], dp[n-1] > 0
dp[n] = nums[n], dp[n-1] <= 0
或者 dp[n] = max(dp[n-1] + nums[n], nums[n])
因为
dp[n-1] > 0 时， 加上 dp[n-1] 对 dp[n] 有增益作用。
dp[n-1] < 0 时, 加上 dp[n-1] 只会使 dp[n] 更小
初始条件为 dp[0] = nums[0]
从头到尾计算出 dp[0] 到 dp[n]， 计算过程中出现过的最大 dp[i] 就是整个数组的 最大连续子序列和

可以使用滚动数组的空间优化方法来省略 dp 数组，只使用一个变量 pre 保存前一个 dp 值，将空间复杂度降到 O(1)。

时间复杂度 O(n) 空间复杂度 O(1)

2020年2月

private static class SolutionV202002 {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            sum = sum > 0 ? sum + nums[i] : nums[i];
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }
}

2020年5月

5月份每日一题遇到这道题，知道是动态规划，也直接就想出了递推公式，但还是给写复杂了
其实并不要一个 int[] sum 数组来保存子数组的最大和，一个变量 sum 即可，因为 i-1 之前的结果已经没有用了。

private static class SolutionV202005 {
    public int maxSubArray(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        int max = nums[0];
        // sum[i] 表示 nums[0...i] 中以 nums[i] 为结尾的连续子数组的最大和
        // 则 sum[i] = sum[i-1] + nums[i] if sum[i-1] > 0, or sum[i] = nums[i]
        int[] sum = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i - 1 >= 0 && sum[i - 1] > 0) {
                sum[i] = sum[i - 1] + nums[i];
            } else {
                sum[i] = nums[i];
            }
            max = Math.max(max, sum[i]);
        }
        return max;
    }
}

线段树分治法

---

GitHub代码

algorithms/leetcode/leetcode/_053_MaximumSubarray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_053_MaximumSubarray.java

---