算法分析例子：MaxSubSum问题
问题
给定整数\(A_1, A_2, ..., A_N,\)求\(\sum_{k=i}^{j}A_k\)的最大值，其中\(A_i\)有可能是负数。这里把使得\(\sum_{k=i}^{j}A_k\)最大的序列称为最大连续子序列。
求解的算法
方法一
暴力枚举出所有可能的子序列的起点和终点，并求出对应子序列的和，从中选出最大值。算法使用了三层循环，一层用来枚举起点，一层用来枚举终点，还有一层用来求和。每一层循环的最大迭代次数都是n，故算法的时间复杂度为\(O(n \times n \times n) = O(n^3)\)。
/**
* triple loop solution, time complexity is cubic
*/
public static int maxSubSum1(int[] array) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
int thisSum = 0;
for (int k = i; k <= j; k++) {
thisSum += array[k];
}
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
方法二
方法二是方法一的改进。因为\(\sum_{k=i}^{j} = A_j + \sum_{k=i}^{j-1}\)，所以方法一的三层循环可以改为两层循环：第一层循环枚举所有可能的连续子序列起点；第二层循环在起点到数组末尾的区间内从前往后累加，这相当于不断将终点延后一个位置直至数组末尾。累加过程中的最大值即是所求的最大连续子序列之和。这两层循环的时间复杂度是\(O(n \times n) = O(n^2)\)。
/**
* double loop solution, time complexity is quadratic
*/
public static int maxSubSum2(int[] array) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
int thisSum = 0;
for (int j = i; j < array.length; j++) {
thisSum += array[j];
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
方法三
方法三是分而治之的递归算法。首先将序列从中间分割成两部分，那么最大连续子序列可能的位置有三种：
- 完全位于左半部分
- 完全位于右半部分
- 横跨左右两部分
分别计算出三种位置中的最大连续子序列，它们中序列和最大的那一个就是所求的结果。
对于第一和第二种位置，分别对左右两半部分进行递归调用即可；对于第三种位置，从中间开始向左右延伸，分别计算出与中间接壤的左右最大连续子序列，将这两个子序列加起来就是第三种位置的最大连续子序列。
令\(T(N)\)为求解规模为N的最大连续子序列问题时所花费的时间。在基准情况下，即N=1时，求解时间是常数的，因此我们记\(T(1)=1\)。当\(N>1\)时，算法会产生两个耗时\(T(N/2)\)的递归调用，而计算出第三种位置的最大连续子序列可能需要扫描整个数组，故其时间复杂度为\(O(N)\)。综上所述，我们有方程组 \(\begin{aligned} T(1) = 1 \\ T(N) = 2T(N/2) + O(N) \\ \end{aligned}\)
在大O分析中，我们可以将O(N)替换为N，得到\(T(N) = 2T(N/2) + N\)。假设\(N=2^k\)，结合\(T(1) = 1\)我们可以得到并观察出 \(\begin{aligned} T(2) = 2*1 + 2 = 4 = 2 * (log2 + 1) \\ T(4) = 2*4 + 4 = 12 = 4 * (log4 + 1) \\ T(8) = 2*12 + 8 = 32 = 8 * (log8 + 1) \\ \end{aligned}\) 通过数学归纳法，我们可以求出通项公式\(T(N) = N * (k+1) = N*log(N) + N = O(N*log(N))\)，也就是说方法三的时间复杂度为\(O(N*log(N))\)。
/**
* recursive divide and conquer solution, time complexity is n*log(n)
*/
private static int maxSubSumRecursive(int[] array, int left, int right) {
if (left == right) {
return array[left];
}
int maxSum = Integer.MIN_VALUE;
int middle = (left + right) / 2;
int leftMaxSubSum = maxSubSumRecursive(array, left, middle);
int rightMaxSubSum = maxSubSumRecursive(array, middle + 1, right);
int leftBorderMaxSubSum = Integer.MIN_VALUE;
int tempSum = 0;
for (int i = middle; i >= left; i--) {
tempSum += array[i];
if (tempSum > leftBorderMaxSubSum) {
leftBorderMaxSubSum = tempSum;
}
}
int rightBorderMaxSubSum = Integer.MIN_VALUE;
tempSum = 0;
for (int i = middle + 1; i <= right; i++) {
tempSum += array[i];
if (tempSum > rightBorderMaxSubSum) {
rightBorderMaxSubSum = tempSum;
}
}
maxSum = Math.max(Math.max(leftMaxSubSum, rightMaxSubSum), leftBorderMaxSubSum + rightBorderMaxSubSum);
return maxSum;
}
/**
* driver function of maxSubRecursive
*/
public static int maxSubSum3(int[] array) {
return maxSubSumRecursive(array, 0, array.length - 1);
}
方法四
方法四在扫描数组的同时进行累加。当累加结果为负数时，把累加值重置为0。这相当于抛弃前面的序列，重新进行累加。在扫描累加的过程中维持一个最大累加值的记录，扫描结束后的最大累加值就是所求的结果。
重置为0的操作不会使我们错过最优解，这是因为负数对于后续的求解没有作用，加上一个负数的连续子序列必然不是最大的。方法四把所有大于0的连续子序列都考虑进来了，因此可以保证最优解不会被遗漏。
PS：当数组中的所有元素均为负数时，算法会返回一个最小的负数元素。
方法四只扫描一遍数组，其时间复杂度仅为\(O(n)\)。
/**
* linear time solution
*/
public static int maxSubSum4(int[] array) {
int maxSum = Integer.MIN_VALUE;
int thisSum = 0;
for (int i = 0; i < array.length; i++) {
thisSum += array[i];
if (thisSum > maxSum) {
maxSum = thisSum;
}
if (thisSum < 0) {
thisSum = 0;
}
}
return maxSum;
}