Maximum Subarray

LeetCode Q 53 - Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

Solution 1: DP

public int maxSubArray(int[] nums) {
	if (nums == null || nums.length == 0) return 0;

	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	int maxSum = nums[0];
	for (int i = 1; i < nums.length; i++) {
		if (dp[i - 1] <= 0) dp[i] = nums[i];
		else dp[i] = dp[i - 1] + nums[i];
		maxSum = Math.max(maxSum, dp[i]);
	}

	return maxSum;
}

Solution 2: Divide and Conquer

A quite clean but detailed explanation can be found here.

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

private int sum (int[] nums, int left, int right) {
	if (left == right) return nums[left];
	
	int mid = left + (right - left) / 2;
	int leftSum = sum(nums, left, mid);
	int rightSum = sum(nums, mid + 1, right);
	int crossSum = crossSum(nums, left, right);
	
	return Math.max(leftSum, Math.max(rightSum, crossSum));
}

private int crossSum(int[] nums, int left, int right) {
	int leftSum = Integer.MIN_VALUE, rightSum = Integer.MIN_VALUE, sum = 0;
	int mid = left + (right - left) / 2;
	for (int i = mid; i >= 0; i--) {
	    sum += nums[i];
	    if (leftSum < sum) leftSum = sum;
	}
	
	sum = 0;
	for (int i = mid + 1; i <= right; i++) {
	    sum += nums[i];
	    if (rightSum < sum) rightSum = sum;
	}
	
	return leftSum + rightSum;
}