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

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.

public class Solution {
    public int maxSubArray(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int preMax = Integer.MIN_VALUE,
            accuSum = -1,
            start = -1, 
            end = -1,
            lastIndex = -1;
        
        for(int i=0;i<A.length;i++){
            if(accuSum<0){
                lastIndex=i;
                accuSum=A[i];
            }else{
                accuSum+=A[i];
            }
            if(accuSum>=preMax){
                start=lastIndex;
                end=i;
                preMax = accuSum;
            }
        }
        return preMax;
    }
}

Divide and Conquer 

public class Solution {
    public int maxSubArray(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
       int[] res = maxSubArray(A,0,A.length-1);
       return res[0];
    }
    
    public int[] maxSubArray(int [] A, int start, int end){
        int[] res = new int[4];
            
        if(start==end){
            res[0]=A[start];
            res[1]=A[start];
            res[2]=A[start];
            res[3]=A[start];
        }else if(start<end){
            int mid=(start+end)/2;
            int[] left = maxSubArray(A, start,mid);
            int[] right = maxSubArray(A, mid+1,end);
            
            res[3]=left[3]+right[3];
            res[2]=Math.max(right[2],right[3]+left[2]);
            res[1]=Math.max(left[1],left[3]+right[1]);
            
            res[0] = Math.max(right[0],Math.max(left[0],left[2]+right[1]));
        }
        return res;
    }
}