Maximum Subarray

MaximumSubarray.java

/**
 * 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) {
        int res = A[0], sum = 0;
        for(int i = 0; i < A.length; ++i){
            sum = Math.max(sum + A[i], A[i]);
            res = Math.max(res, sum);
        }
        return res;
    }
}

MaximumSubarrayDivideandConquer.java

/**
 * 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) {
    	if (A.length == 0)
			return 0;
		return maxSubArray(A, 0, A.length - 1);
	}

	// overloading...
	public int maxSubArray(int[] A, int low, int high) {
		int leftMidSum = Integer.MIN_VALUE, rightMidSum = Integer.MIN_VALUE, sum = 0;
		if (low == high)
			return A[low];
		int mid = low + (high - low) / 2;
		int maxLeftSum = maxSubArray(A, low, mid);
		int maxRightSum = maxSubArray(A, mid + 1, high);
		// across sum
		for (int i = mid; i >= low; i--) {
			sum += A[i];
			leftMidSum = (sum > leftMidSum) ? sum : leftMidSum;
		}
		// reset sum as 0
		sum = 0;
		for (int i = mid + 1; i <= high; i++) {
			sum += A[i];
			rightMidSum = (sum > rightMidSum) ? sum : rightMidSum;
		}
		return max3(maxLeftSum, maxRightSum, (leftMidSum + rightMidSum));
	}

	public int max3(int a, int b, int c) {
		return a > b ? (a > c ? a : c) : (b > c ? b : c);
	}
}

Correction: sum=A[0] instead of sum=0.
Try for input: [2, -1, 4]