下载掌阅APP，畅读海量书库
立即打开
最大连续子序列和：改进算法 O ( n log n )
最大连续子序列和的问题还可以用分治法解决。假设输入的整数序列是{4,−3,5,−2,−1,2,6,−2}，这个输入可以被划分成两部分，即前4个元素和后4个元素。这样使和值最大的连续子序列可能出现在下面3种情况中。
情况1：使和值最大的连续子序列位于前半部分。
情况2：使和值最大的连续子序列位于后半部分。
情况3：使和值最大的连续子序列从前半部分开始但在后半部分结束。
这3种情况中，使和值最大的连续子序列就是本问题的解。
前两种情况下，只需要在前半部分或后半部分找最大连续子序列，这通过递归调用就可以解决。问题是第三种情况下怎么办？可以从前后两部分的边界开始，通过从右到左的扫描找到左半段的最大连续子序列；类似地，通过从左到右的扫描找到右半段的最大连续子序列。把这两个连续子序列组合起来，形成跨越中点的最大连续子序列。在上述输入的整数序列中，通过从右到左扫描得到左半段的最大连续子序列和是4，包括前半部分的所有元素。从左到右扫描得到的右半段的最大连续子序列和是7，包括−1、2和6这3个元素。因此，从前半部分开始但在后半部分结束的最大连续子序列和为4+7=11，使和值最大的连续子序列是{4,−3,5,−2,−1,2,6}。
总结一下，用分治法解决最大连续子序列和问题的算法包括4个步骤。
（1）递归地计算位于前半部分的最大连续子序列。
（2）递归地计算位于后半部分的最大连续子序列。
（3）通过循环查找以左半段某处为起点，以中点为终点的连续子序列和的最大值，以及以中点为起点，以右半段某个位置为终点的连续子序列和的最大值，计算从前半部分开始但在后半部分结束的最大连续子序列的和。
（4）选择上述3个步骤中得出的使和值最大的连续子序列，作为整个问题的解。
根据此算法，可编写代码清单1-4所示的程序。由于此方案采用了递归算法，所以函数包含控制递归的参数left和right。这个函数原型与前文所用的原型不同，在实际应用时并不需要传入left和right的值，所以需要定义一个包裹函数。
代码清单1-4 最大连续子序列和的 O ( n log n )递归算法
// 递归解决方案
int maxSum(int a[], int left, int right, int &start, int &end) {
int maxLeft, maxRight, center;
// maxLeft和maxRight分别为前半部分、后半部分的最大连续子序列和
int leftSum = 0, rightSum = 0; // 情况3中，左、右半段的连续子序列和
int maxLeftTmp = 0,
maxRightTmp = 0; // 情况3中，左、右半段的最大连续子序列和
int startL, startR, endL,
endR; // 前半部分、后半部分的最大连续子序列的起点和终点
if (left == right) { // 仅有一个元素，递归终止
start = end = left;
return a[left] > 0 ? a[left] : 0;
}
center = (left+right) / 2;
// 找前半部分的最大连续子序列和
maxLeft = maxSum(a, left, center, startL, endL);
// 找后半部分的最大连续子序列和
maxRight = maxSum(a, center+1, right, startR, endR);
// 找从前半部分开始但在后半部分结束的最大连续子序列
start = center;
for (int i = center; i >= left; --i) {
leftSum+= a[i];
if (leftSum > maxLeftTmp) {
maxLeftTmp = leftSum;
start = i;
}
}
end = center+1;
for (int i = center+1; i <= right;++i) {
rightSum+= a[i];
if (rightSum > maxRightTmp) {
maxRightTmp = rightSum;
end = i;
}
}
// 找3种情况中的最大连续子序列和
if (maxLeft > maxRight)
if (maxLeft > maxLeftTmp+maxRightTmp) {
start = startL;
end = endL;
return maxLeft;
} else
return maxLeftTmp+maxRightTmp;
else if (maxRight > maxLeftTmp+maxRightTmp) {
start = startR;
end = endR;
return maxRight;
} else
return maxLeftTmp+maxRightTmp;
}
// 包裹函数
int maxSubsequenceSum(int a[], int size, int &start, int &end) {
return maxSum(a, 0, size - 1, start, end);
} 代码清单1-4的时间复杂度是 O ( n log n )。递归函数的时间复杂度的计算较为复杂，本书将在7.5.2节和7.6节介绍递归函数时间复杂度的计算。