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.

经典题目，有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);
	}
}

LeetCode | Maximum Subarray,布布扣,bubuko.com

LeetCode | Maximum Subarray

原文：http://blog.csdn.net/perfect8886/article/details/22427909