题目描述

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

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

https://leetcode-cn.com/problems/maximum-subarray/

解法1 – 使用DP，O(n)

我们定义与nums同型的一维数组dp，dp[i]表示必须使用nums[i]元素，得到的连续子数组的最大和。那么有dp[i] = max(nums[i], dp[i – 1] + nums[i])。

解释一下，如果前面累积的最大和是负数，那么使用累积的和与nums[i]相加会使得和更小，我们还不如直接使用nums[i]作为新的连续子数组。

时间复杂度O(n)，空间复杂度O(n)。全部代码如下：

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

我们观察到dp[i]只依赖于dp[i-1]，因此我们可以使空间复杂度压缩到O(1)。

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int prevSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            prevSum = Math.max(prevSum, 0) + nums[i];
            maxSum = Math.max(maxSum, prevSum);
        }

        return maxSum;
    }
}

解法2 – 分治法，O(nlogn)

我们定义函数maxSubArray(nums, l, r)，表示区间[l, r]内找到的连续子数组的最大和。那么在区间[l, r]内的连续子数组最大和有3种来源：

1. 来源于[l, m) (m = (l + r) / 2)，记为max1;
2. 来源与(m, r]，记为max2;
3. 来源于跨中间元素m的区间，记为max3

那么[l, r]区间的连续子数组最大和有max(max1, max2, max3)。其中，第3种情况比较复杂。我们需要从m的左右两侧出发，通过扫描来求和，如图1所示。

我们递归求解区间[l, r]的连续子数组的最大值，取max1、max2、max3中三者最大的作为[l, r]的连续子数组最大和，然后返回。

我们定义maxSubArray(nums, l, r)为f(n)（n = r – l + 1），那么调用一次maxSubArray有f(n) = n + 2*f(n / 2)。通过数学归纳法能推导出maxSubArray的时间复杂度为O(n(logn + 1)) => O(nlogn)。全部代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        return maxSubArray(nums, 0, nums.length - 1);
    }

    private int maxSubArray(int[] nums, int l, int r) {
        if (l > r) return Integer.MIN_VALUE;

        int m = (l + r) >>> 1;

        int max1 = maxSubArray(nums, l, m - 1);
        int max2 = maxSubArray(nums, m + 1, r);

        int leftMax = 0;

        for (int i = m - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            leftMax = Math.max(leftMax, sum);
        }

        int rightMax = 0;
        for (int i = m + 1, sum = 0; i <= r; i++) {
            sum += nums[i];
            rightMax = Math.max(rightMax, sum);
        }

        int max3 = leftMax + rightMax + nums[m];

        return Math.max(Math.max(max1, max2), max3);
    }
}

参考：

https://leetcode.com/problems/maximum-subarray/discuss/199163/Python-O(N)-Divide-and-Conquer-solution-with-explanations

https://leetcode.com/problems/maximum-subarray/discuss/20452/C%2B%2B-DP-and-Divide-and-Conquer