Question:
Find the contiguous subarray within an array (containing at least one number) that has the largest sum.
For example,
given the array [2, 1, –3, 4, –1, 2, 1, –5, 4],
The contiguous array [4, –1, 2, 1] has the largest sum = 6.
此问题提供了两种解决方案，首先是L+A[M]+R模式，把一个问题分解为左右及中间三部分。若是包含中间部分则直接输出最大值，否则为L或R，并重复前面的操作。
O(n log n) runtime, O(log n) stack space
public int maxSubArray(int[] A) {
return maxSubArrayHelper(A, 0, A.length - 1);
}
private int maxSubArrayHelper(int[] A, int L, int R) {
if (L > R) return Integer.MIN_VALUE;
int M = (L + R) / 2;
int leftAns = maxSubArrayHelper(A, L, M - 1);
int rightAns = maxSubArrayHelper(A, M + 1, R);
int lMaxSum = 0;
int sum = 0;
for (int i = M - 1; i >= L; i--) {
sum += A[i];
lMaxSum = Math.max(sum, lMaxSum);
}
int rMaxSum = 0;
sum = 0;
for (int i = M + 1; i <= R; i++) {
sum += A[i];
rMaxSum = Math.max(sum, rMaxSum);
}
return Math.max(lMaxSum + A[M] + rMaxSum, Math.max(leftAns, rightAns));
}
注：读代码时，从整体到部分，不要一下子陷入到递归中。
第二种解决方案，动态编程（DP）。
O(n) runtime, O(1) space
若f(k)是截止到下标为k时的最大值，那么一定满足 f(k) = max( f(k-1) + A[k], A[k] )，这样就找到了f(k) 与 f(k-1) 的关系。这样，用两个标记，一个记载到k处的最大值，一个更新当前的最大值。
public int maxSubArray(int[] A) {
int maxEndingHere = A[0], maxSoFar = A[0];
for (int i = 1; i < A.length; i++) {
maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
maxSoFar = Math.max(maxEndingHere, maxSoFar);
}
return maxSoFar;
}