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);
	}
}