Maximum Subarray

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.

Naive Way: 一个感觉觉得跟sell stock那题很像，可以用DP吧，先试一试。

基本逻辑为：
opt[i,j] // 表示从i到j的maximum subarray。
才写第一句就发现这样一来就是O(n^2）的复杂度了。但是感觉这一题应该是能在O(n)的时间内算出来的。

一个比较直观的想法就是用指针控制记录有效区段首尾。一旦遇到整数，就有可能要替换最大值，一旦遇到负数，只要当前和仍大于零，就可以将该负数加入有效区段内。这里自己还漏掉了全是负数的情况 ，但这种情况其实很简单，全是负数时最大的和就是其中一个负数，每次取到负数都与最大值进行比较则可将该情况囊括。


public class Solution {
    public int maxSubArray(int[] A) {
        int begin = 0, end = 0;
        if(A.length == 0){return 0;}
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0;i < A.length;i++){
            if(A[i] >= 0){
                if(sum <= 0){
                    while(begin!=end){begin++;}
                    sum = 0;
                }
                max = Math.max(sum + A[i], max);
            }else{
                max = Math.max(max,A[i]);
            }
            end++;
            sum += A[i];
        }
        return max;
    }
}


最后看来一个人的discuss发现跟我的一模一样，就是没有begin 和 end。这才发现begin和end在这段代码中没有作用，删除掉。

public class Solution {
    public int maxSubArray(int[] A) {
        if(A.length == 0){return 0;}
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0;i < A.length;i++){
            if(A[i] >= 0){
                if(sum <= 0)
                    sum = 0;
                max = Math.max(sum + A[i], max);
            }else{
                max = Math.max(max,A[i]);
            }
            sum += A[i];
        }
        return max;
    }
}

最终版本应该是这样的：（来自leetcode用户 AlexTheGreat）

public int maxSubArray(int[] A) {
    int max = Integer.MIN_VALUE, sum = 0;
    for (int i = 0; i < A.length; i++) {
        if (sum < 0) 
            sum = A[i];
        else 
            sum += A[i];
        if (sum > max)
            max = sum;
    }
    return max;
}

Improved Way: 看见leetcode上有人提问这道题用divide and conquer做，

一位大神回答了说divide and conquer是 O(nlogn)。那么就懂如果要

divide and conquer是怎么回事，每次都得对比两边的最大subarray sum和

中间部分有可能的subarray sum,想想都觉得很麻烦，还是先不写了。