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.

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. public class Solution {
  2.   public int maxSubArray(int[] nums) {
  3.     return maxSubArray(nums, 0, nums.length - 1);
  4.   }
  6.   int maxSubArray(int[] nums, int lo, int hi) {
  7.     if (lo == hi) {
  8.       return nums[lo];
  9.     }
  11.     int mid = lo + (hi - lo) / 2;
  13.     int left = maxSubArray(nums, lo, mid);
  14.     int right = maxSubArray(nums, mid + 1, hi);
  15.     int middle = maxMiddleSum(nums, lo, mid, hi);
  17.     return Math.max(middle, Math.max(left, right));
  18.   }
  20.   int maxMiddleSum(int[] nums, int lo, int mid, int hi) {
  21.     int sum = 0;
  23.     int left = Integer.MIN_VALUE;
  24.     for (int i = mid; i >= lo; i--) {
  25.       sum += nums[i];
  26.       left = Math.max(left, sum);
  27.     }
  29.     sum = 0;
  31.     int right = Integer.MIN_VALUE;
  32.     for (int i = mid + 1; i <= hi; i++) {
  33.       sum += nums[i];
  34.       right = Math.max(right, sum);
  35.     }
  37.     return left + right;
  38.   }
  39. }