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.

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:

Method 1: prefix sum

The maximum subarray that ends at index i, is the prefix sum at i, minus the minimum prefix sum before i.

If we can find all the maximum subarray that end at index 0, 1, 2, ...., we take the maximum of them, which is the maximum subarray of the input array.

We go through the input array once, so the time complexity is O(n).



Code:

public class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int min = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum - min);
            min = Math.min(min, sum);
        }
        return max;
    }
}

Method 2: DP (Kadane's Algorithm)

The maximum subarray that ends at index i, is the maximum of:

1. maximum subarray that ends at index i - 1, plus nums[i]

2. nums[i]



Code:

public class Solution {
    public int maxSubArray(int[] nums) {
        int localMax = nums[0];
        int globalMax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            localMax = Math.max(localMax + nums[i], nums[i]);
            globalMax = Math.max(globalMax, localMax);
        }
        return globalMax;
    }
}

Method 3: Divide & Conquer

Recursively split the input array into three parts:

nums[start ~ mid - 1]
nums[mid]
nums[mid + 1 ~ end]

Find the maximum subarray in nums[start ~ mid - 1].

Find the maximum subarray in nums[mid + 1 ~ end].

Find the maximum subarray which includes nums[mid];

Return the max of the above three.

Time complexity: We use O(n) operation and leave two T(n/2) problems.
T(n) = 2T(n/2) + O(n) => T(n) = O(nlogn)



Code:

public class Solution {
    public int maxSubArray(int[] nums) {
        return findMax(nums, 0, nums.length - 1);
    }
    
    public int findMax(int[] nums, int start, int end) {
        if (start > end) {
            return Integer.MIN_VALUE;
        }
        
        if (start == end) {
            return nums[start];
        }
        
        int mid = start + (end - start) / 2;
        
        // max subarray in left subarray
        int leftMax = findMax(nums, start, mid - 1);
        
        // max subarray in right subarray
        int rightMax = findMax(nums, mid + 1, end);
        
        
        // max subarray which includes nums[mid]
        
        // go left (nums[mid] is included in max subarray)
        int sum = nums[mid];
        int midMax = nums[mid];
        for (int i = mid - 1; i >= start; i--) {
            sum += nums[i];
            midMax = Math.max(midMax, sum);
        }
        
        // go right
        sum = midMax;
        for (int i = mid + 1; i <= end; i++) {
            sum += nums[i];
            midMax = Math.max(midMax, sum);
        }
        

        return Math.max(midMax, Math.max(leftMax, rightMax));
    }
}