maxSubarray.java

/*
	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.

*/

public class Solution {
    public int maxSubArray(int[] A) {
        if(A==null || A.length==0) return 0;
        int result=A[0], curr=A[0];
        for(int i=1; i<A.length; i++){
            if(curr>=0){ // if curr>=0, then result might be lager. Take curr as condition instead of A[i].
                curr+=A[i];
            }else{
                curr=A[i];
            }
            result=Math.max(curr, result);
        }
        return result;
    }
}

// The following solutions come from Tao Hu. 
// http://en.wikipedia.org/wiki/Maximum_subarray_problem
// Kadane's Algorithm (1984)

// Dynamic Programming
// sum -- the max subarray sum ending at current value
// max -- the max subarray sum found so far
// In each day, we check the previous max, if max>0, we add current value to the subarray
// if max<0, we choose current day as a new starting point for subarray
// time: O(n); space: O(1)
public class Solution {
    public int maxSubArray(int[] A) {
        if (A==null || A.length==0) return 0;
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i=0; i<A.length; i++){
            // if sum+A[i] < A[i], we start a new subarray
            sum = Math.max(A[i], sum+A[i]); 
            max = Math.max(sum, max);
        }
        return max;
    }
}

// Divide and Conquer
// time: O(nlgn); space: O(1)
public class Solution {
    public int maxSubArray(int[] A) {
        if (A==null || A.length==0) return 0;
        return finder(A, 0, A.length-1);
    }
    
    public int finder(int[] A, int start, int end)
        if (start > end)    return Integer.MIN_VALUE;
        int mid = start + ((end - start)>>1);           // notice here, cannot omit the out-nested brackets
        int left=Integer.MIN_VALUE, right=Integer.MIN_VALUE, sum=0;
        for (int i=mid+1; i<=end; i++){
            sum += A[i];
            right = Math.max(sum,right);
        }
        sum = 0;
        for (int i=mid-1; i>=start; i--){
            sum += A[i];
            left = Math.max(sum, left);
        }
        int mmax = A[mid] + Math.max(left, 0) + Math.max(right, 0);
        return Math.max(mmax, Math.max(finder(A, start, mid-1), finder(A, mid+1, end)));
    }
}