Maximum Subarray

Q:
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.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

A:
----------CLRS 上的  divide and conquer 算法

public class Solution {
    public int maxSubArray(int[] A) {
        // same with the buy&sell stock problem
        return maxSubArray(A,0,A.length-1);
    }

    private int maxSubArray(int[] A, int low, int high) {
        if(low==high){
            return A[low];
        }else{  // low < high
            int mid = (low+high)/2;
            int maxLeft = maxSubArray(A,low,mid);
            int maxRight = maxSubArray(A,mid+1,high);
            int maxCross = maxCrossArray(A,low,mid,high);
            return Math.max(maxRight, Math.max(maxLeft, maxCross));
        }
    }

    private int maxCrossArray(int[] A, int low, int mid, int high) {
        // left part
        int sum = 0 ,maxLeftSum = A[mid];
        for(int i =mid;i>=low;i--){
            sum += A[i];
            if(sum>maxLeftSum){
                maxLeftSum = sum;
            }
        }
        // right part
        sum = 0;
        int maxRightSum = A[mid+1];
        for(int i = mid+1;i<=high;i++){
            sum+=A[i];
            if(sum>maxRightSum){
                maxRightSum = sum;
            }
        }
        return maxLeftSum + maxRightSum;
    }
}

----------------------Kadane's algorithm   ----------- O(n)  ---
-------IDEA: keep two values, maxSoFar, maxEndingHere------------从前面开始，逐个加入数组的值。--------

public class Solution {
       public int maxSubArray(int[] A) {
        int maxSoFar = Integer.MIN_VALUE/2;
        int maxEndHere = Integer.MIN_VALUE/2;
        for (int i = 0; i < A.length; i++) {
            if (maxEndHere <= 0) {
                maxEndHere = A[i];
            } else {
                maxEndHere += A[i];
            }
            // update max_so_far
            if (maxEndHere > maxSoFar) {
                maxSoFar = maxEndHere;
            }
        }
        return maxSoFar;
    }
}

-------------------第二遍------------------就是用空间换时间-----------

public class Solution {
       public int maxSubArray(int[] A) {
        // space to time
        int n = A.length;
        if(n==0)
            return 0;
        int maxSum[] = new int[n]; // max sum till current position
        maxSum[0] = A[0];
        for(int i =1;i<n;i++){
            maxSum[i] = Math.max(A[i], A[i]+maxSum[i-1]);
        }
        // find maxsum value in maxSum
        int result = maxSum[0];
        for(int i =1;i<n;i++){
            if( result < maxSum[i] ) 
                result = maxSum[i];
        }
            return result;
    }
}

-----------------3 rd Pass -----------不用数组空间， 只需要一个变量，记录max sum value  ending here 即可------
对比上面的实现， 是  利用    语句

A[i] + Math.max(0,maxEndHere);

中， A[i] 在外边，  这样，保证了后面的，不会溢出。就是说，避免了像上面那样， Integer,MIN_VALUE +  负数 的情况出现

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

注意： 这里，  其实A.length==0的情况， LC的test case 中估计是没有出现。 或者说，没有定义。  因此，当A为空的时候， 我们这里返回最小值是可以的。

---------------4th pass------------------------
思路就是：  把所有的全加起来，这样，和就是现在这个减前一个最小的即可。

public class Solution {
    public int maxSubArray(int[] A) {
        if(A==null || A.length == 0)
            return 0;
        for(int i =1;i<A.length;i++)
            A[i] += A[i-1];
        int minLeft = 0,result = A[0];
        for(int i =0; i<A.length;i++){
            result = Math.max(result, A[i] - minLeft);
            if(A[i]<minLeft)
                minLeft = A[i];
        }
        return result;
    }
}

Mistakes:
1： minLeft刚开始没有想象成是-1的位置。  转而设置成 Integer.MIN_VALUE了。这样是不对的


Learned: