LeetCode | 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.

click to show 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.

经典题目，有O(n)的遍历一遍的解法（解法1）。

此外，题目还要求用分治法（解法2），需要注意的是，需要求取合并位置向两边扩展能够得到的最大子数组值。

解法1

public class MaximumSubarray {
	public int maxSubArray(int[] A) {
		int max = A[0];
		int sum = A[0];
		for (int i = 1; i < A.length; ++i) {
			sum = Math.max(sum + A[i], A[i]);
			max = Math.max(max, sum);
		}
		return max;
	}
}

public class MaximumSubarray {
	public int maxSubArray(int[] A) {
		return solve(A, 0, A.length - 1);
	}

	private int solve(int[] A, int low, int high) {
		if (low == high) {
			return A[low];
		}
		int mid = low + (high - low)/ 2;
		int leftMax = solve(A, low, mid);
		int rightMax = solve(A, mid + 1, high);
		int leftSum = A[mid];
		int sum = A[mid];
		for (int i = mid - 1; i >= low; --i) {
			sum += A[i];
			leftSum = Math.max(leftSum, sum);
		}
		int rightSum = A[mid + 1];
		sum = A[mid + 1];
		for (int i = mid + 2; i <= high; ++i) {
			sum += A[i];
			rightSum = Math.max(rightSum, sum);
		}
		return Math.max(Math.max(leftMax, rightMax), leftSum + rightSum);
	}
}