53. Maximum Subarray

题目描述：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
即找出一个给定数组中加和最大的连续子数组。

第一个直观解法，就是把每个元素作为子数组的起始元素，找出和最大的子数组，伪代码：

    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int tmpSum = 0;
        for (int j = i; j < nums.length; j++) {
            tmpSum += nums[j];
            if (tmpSum > max) {
                max = tmpSum;
            }
        }
    }

这里可以做一些优化，就是定义一个前缀和数组int[] sum，这样求i到j的和就变为了sum[j] - sum[i]，避免了每次都要重复的加运算，当然这个解法时间复杂度还是n方会超时。

第二种解法：动态规划。
每个元素都会是n个子数组的末尾元素，那么这些子数组中肯定有一个是有最大和的。如果知道了以第n个元素为末尾的最大子数组和，求第n+1就很好知道了。以sum[n]表示第n个元素为末尾的最大子数组和，如果sum[n]大于等于0，那么sum[n+1] = sum[n] + num[n+1]；否则sum[n+1] = num[n+1]。

public int maxSubArray1(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1] : 0);
        max = Math.max(max, dp[i]);
    }

    return max;
}

可以观察到求dp[i]的时候只与dp[i-1]有关，所以这里空间上可以再压缩，dp只需要声明为大小为两个元素的数组。

public int maxSubArray2(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;
    int[] dp = new int[2];
    dp[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i%2] = nums[i] + (dp[(i-1)%2] > 0 ? dp[(i-1)%2] : 0);
        max = Math.max(max, dp[i%2]);
    }

    return max;
}

但是leetcode上这种写法比前一种要慢，可能是取模运算的问题吧。

看这道题目的标签还有分治方法，自己没想出来，翻看discuss找到了。这种解法的思路是：找到数组的middle元素，那么这个middle元素可能在最大子数组中，也可能不在；如果不在，那么最大子数组要么在middle左侧，要么在middle右侧；最后求左侧、右侧、和包含middle的最大数组三者的最大值就是结果了。

public int maxSubArray3(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    return divideConquer(nums, 0, nums.length - 1);
}

private int divideConquer(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    int middle = left + (right - left) / 2;
    int leftRes = divideConquer(nums, left, middle);
    int rightRes = divideConquer(nums, middle + 1, right);

    int leftMax = nums[middle];
    int rightMax = nums[middle + 1];
    int tmp = 0;
    for (int i = middle; i >= left; i--) {
        tmp += nums[i];
        leftMax = Math.max(leftMax, tmp);
    }
    tmp = 0;
    for (int i = middle + 1; i <= right; i++) {
        tmp += nums[i];
        rightMax = Math.max(rightMax, tmp);
    }

    return Math.max(leftMax + rightMax, Math.max(leftRes, rightRes));
}