[LeetCode]Maximum Subarray

是一道题的解法可以带出十道题解法的题目，首先我们定义两个变量，localMax[i]为以i结尾的subarray中最大的值，globalMax[i]定义为[0, i]范围中最大的subarray(subarray不一定需要已i结尾)。递推表达式是：

• localMax[i] = max(localMax[i - 1] + A[i], A[i]);
• globalMax[i] = max(globalMax[i - 1], localMax[i]);

根据这个表达式我们只需要从左向右扫一遍就可以了，时间复杂度O(n)，然后空间可以优化到O(1)，代码如下：

	public class Solution {
	public int maxSubArray(int[] A) {
	if (A == null)
	return 0;
	int len = A.length;
	if (len < 1)
	return 0;
	int max = Integer.MIN_VALUE, currSum = 0;
	for (int i = 0; i < len; i++) {
	int localMax = currSum + A[i];
	max = localMax >= max? localMax: max;
	currSum = localMax <= 0? 0: localMax;
	}
	return max;
	}
	}

view raw maximum subarray v-1.java hosted with ❤ by GitHub

另外还有个divide and conquer，分成两半，找左边右边和跨过中间的max subarray中的最大值，中间的是很好找的，左边一直扩展记录最大值，右边同样的，然后返回左边最大值加上右边最大值，线性时间可以找到，所以总的时间复杂度是O(n log n)，代码如下：

	public class Solution {
	public int maxSubArray(int[] A) {
	if (A == null)
	return 0;
	int len = A.length;
	if (len < 1)
	return 0;
	return getMax(A, 0, len - 1);
	}
	private int getMax(int[] A, int lo, int hi) {
	if (lo == hi)
	return A[lo];
	int mid = lo + (hi - lo) / 2;
	int left = getMax(A, lo, mid);
	int right = getMax(A, mid + 1, hi);
	int cross = getCross(A, mid, lo, hi);
	return max(left, right, cross);
	}
	private int getCross(int[] A, int mid, int lo, int hi) {
	int leftMax = A[mid], rightMax = A[mid + 1], leftSum = A[mid], rightSum = A[mid + 1];
	for (int i = mid - 1; i >= lo; i--) {
	leftSum += A[i];
	leftMax = leftSum > leftMax? leftSum: leftMax;
	}
	for (int i = mid + 2; i <= hi; i++) {
	rightSum += A[i];
	rightMax = rightSum > rightMax? rightSum: rightMax;
	}
	return leftMax + rightMax;
	}
	private int max(int a, int b, int c) {
	int max = a >= b? a: b;
	return max >= c? max: c;
	}
	}

view raw maximum subarray v-2.java hosted with ❤ by GitHub