Maximum Subarray

Maximum Subarray: http://lintcode.com/en/problem/maximum-subarray/

Three solutions:

// Brute force

// DP version
public int maxSubArray(int[] A) {
    int n = A.length;
    int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
    dp[0] = A[0];
    int max = dp[0];

    for(int i = 1; i < n; i++){
        dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
        max = Math.max(max, dp[i]);
    }

    return max;
}

// Kadane’s Algorithm (actually DP)
// maxSoFar maxEndHere
public static int maxSubArray(int[] A) {
    int maxSoFar=A[0], maxEndingHere=A[0];
    for (int i=1;i<A.length;++i){
        maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
        maxSoFar=Math.max(maxSoFar, maxEndingHere);    
    }
    return maxSoFar;
}

// max and minSum version
public int maxSubArray(int[] nums) {
    // write your code
    int sum = 0;
    int minSum = 0;
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < nums.length; i++){
        sum += nums[i];
        max = Math.max(max, sum - minSum);
        minSum = Math.min(minSum, sum);
    }

    return max;
}

// binary search version
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        return divideAndConquer(nums, 0, nums.length - 1);
    }

    public int divideAndConquer(int[] nums, int low, int high){
        if(low == high){
            return nums[low];
        }

        int mid = (high - low) / 2 + low;

        return Math.max(Math.max(divideAndConquer(nums, low, mid),
                                 divideAndConquer(nums, mid + 1, high)),
                                 crossMid(nums, mid, low, high));
    }

    public int crossMid(int[] nums, int mid, int low, int high){
        int left = mid, right = mid + 1;
        int leftMax = Integer.MIN_VALUE, rightMax = Integer.MIN_VALUE;
        int leftSum = 0, rightSum = 0;
        while(left >= low){
            leftSum += nums[left--];
            leftMax = Math.max(leftMax, leftSum);
        }

        while(right <= high){
            rightSum += nums[right++];
            rightMax = Math.max(rightMax, rightSum);
        }

        return leftMax + rightMax;
    }
}