Maximum Subarray, the Divide and Conquer method

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

Add a DP solution, plus output the maximum subarray.

public class MaxSubArray {
  public int maxSubArray (int[] A)
 {
  if (A == null || A.length == 0)
            return 0;
  //ArrayList maxSub = new ArrayList();
  //maxSub.add(A[0]);
        int local_max = A[0];
        int max = A[0];
        int start = 0;
        int end = 0;
        for (int i = 1; i < A.length; i++)
        {
         local_max = Math.max(local_max + A[i], A[i]);
         if (local_max == A[i])
         {
          start = i;
          end = i;
         }
            max = Math.max(max, local_max);
            if (max == local_max)
             end = i;
        }
        ArrayList maxSub = new ArrayList();
        if (start == end)
         maxSub.add(A[start]);
        else
        {
         for (int i = start; i <= end; i++)
          maxSub.add(A[i]);
        }
        System.out.println(maxSub);
        return max;
 }
}

If we need to do it in the divide and conquer approach, naturally we need to separate the array from the middle. Ok, now we have three conditions.



1. The subarray required is in the left side.
2. The subarray required is in the right side.
3. The subarray required contains the middle element plus some of the elements in the left subarray plus some of the elements in the right subarray.

For the 1st and 2nd two conditions, we can solve by recursion.
For the 3rd condition, from the middle, we need to search the left side, get the maximum sum, then the right side, get the maximum sum and combine everything together.

Note both the search and recursion starts from mid - 1 and mid + 1.
For the cases like: -2, -1, 3, -2, -4, -1. even the right side will return -1, the right most element. Because we will search from the middle, and the smaller elements will not be included since the left_sum and right_sum are both smaller then the middle element.
If the array is: -2, -1, -3, -2, -4, -1. -1 will eventually be returned since the middle array is smaller than right_maximum or left_maximum.

public class MaximumSubarray {
    public int maxSubArray(int[] A) {
        int maxValue = Integer.MIN_VALUE;
        if (A == null || A.length == 0)
            return maxValue;
        maxValue = getMax(A, 0, A.length - 1, maxValue);
        return maxValue;
        
    }
    public int getMax(int[] A, int start, int end, int maxValue)
    {
        if (start > end)
            return Integer.MIN_VALUE;
        int mid = (start + end) / 2;
        int left_max = getMax(A, start, mid - 1, maxValue);
        int right_max = getMax(A, mid + 1, end, maxValue);
        maxValue = Math.max(left_max, maxValue);
        maxValue = Math.max(right_max, maxValue);
        int sum = 0;
        int leftSum = 0;
        int rightSum = 0;
        for (int i = mid - 1; i >= start; i--)
        {
            sum += A[i];
            leftSum = Math.max(leftSum, sum);
        }
        sum = 0;
        for (int i = mid + 1; i <= end; i++)
        {
            sum += A[i];
            rightSum = Math.max(rightSum, sum);
        }
        maxValue = Math.max(maxValue, leftSum + A[mid] + rightSum);
        return maxValue;
    }
}