[LeetCode] Maximum Subarray

Problem:

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: O(n)

public class Solution {
   public int maxSubArray(int[] A) {
      int max = A[0];
      int[] sum = new int[A.length];
      sum[0] = A[0];
 
      for (int i = 1; i < A.length; i++) {
         sum[i] = Math.max(A[i], sum[i - 1] + A[i]);
         max = Math.max(max, sum[i]);
      }
 
      return max;
   }
}
Solution 2: O(n)

public class Solution {
    public int maxSubArray(int[] A) {
        int maxSum = Integer.MIN_VALUE;
        return findMaxSub(A, 0, A.length - 1, maxSum);
    }
     
  
    public int findMaxSub(int[] A, int left, int right, int maxSum) {
        if(left > right)    
           return Integer.MIN_VALUE;
         
        int mid = (left + right) / 2;
        int leftMax = findMaxSub(A, left, mid - 1, maxSum);
        int rightMax = findMaxSub(A, mid + 1, right, maxSum);
        maxSum = Math.max(maxSum, Math.max(leftMax, rightMax));
         
        // mid -> left
        int sum = 0;
        int midLeftMax = 0;
        for(int i = mid - 1; i >= left; i--) {
            sum += A[i];
            if(sum > midLeftMax)    
               midLeftMax = sum;
        }
        sum = 0;
        // mid -> right
        int midRightMax = 0; 
        for(int i = mid + 1; i <= right; i++) {
            sum += A[i];
            if(sum > midRightMax)    
               midRightMax = sum;
        }
         
        maxSum = Math.max(maxSum, midLeftMax+midRightMax+A[mid]);
         
        return maxSum;
    }
}

Key Concept: Use DP is simple or use device and conquer