53 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.

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.

Solution 1: Dynamic Programming(negative value cannot be boarder)

have a currentSum variable to keep track on the current sum, if it's negative, then just replace it with the new coming value. Otherwise, keep adding it

public int maxSubArray(int[] nums) {
        if(nums == null)
        {
            return 0;
        }

        int sumMax = Integer.MIN_VALUE;
        int curSum = 0;

        for(int num : nums)
        {
            if (curSum<0)
            {
                //if current sum is less than 0, then the sum will be bigger if just replace it with the current value
                curSum = num;
            }
            else
            {
                //otherwise just keep adding it to the current sum
                curSum += num;
            }

            sumMax = Math.max(curSum, sumMax);
        }
        return sumMax;
    }

Solution 2: Divide and conquer

1. Divide the array into left and right part, recursively find the maximum sub array in the left and right parts.

2. The third candidate is the subarray cross the mid element (could be calculated in linear time).

3. Then we compare these three result, return the maximum one.

The time is T(N) = 2*T(N/2) + O(N), by master’s theroy the time complexity is O(NlogN). Even though DP is more efficient than Divide and Conquer, but it's a good example for solving problem by Divide and Conquer

public int maxSubArray(int[] nums) {
    if(nums.length == 1) return nums[0];
    return maxSubArrayHelper(nums, 0, nums.length-1);
}

public int maxSubArrayHelper(int[] nums, int start, int end) {
    if(start >= end) return nums[start];
    int mid   = (end-start)/2;
    int left  = maxSubArrayHelper(nums, start, start+mid);
    int right = maxSubArrayHelper(nums, start+mid+1, end);
    int cros  = maxCrossingSubArray(nums, start, start+mid, end);
    return Math.max(cros, Math.max(left, right));
}

public int maxCrossingSubArray(int[] nums, int start, int mid, int end) {
    if (start == end) return nums[start];
    int left = Integer.MIN_VALUE;
    int sum = 0;
    if(start <= mid) {
        for(int i = mid-1; i >= start; i--) {
            sum += nums[i];
            if (sum > left) left = sum;
        }
    }
    int right = Integer.MIN_VALUE;
    if (mid <= end) {
        sum = 0;
        for(int i = mid; i <= end; i++) {
            sum += nums[i];
            if (sum > right) right = sum;
        }
    }
    if(left == Integer.MIN_VALUE) return right;
    if(right == Integer.MIN_VALUE) return left;
    return Math.max(left+right, Math.max(left,  right)); 
}