1.4.3　时间复杂度为O(nlogn)的算法

最大连续子序列和：改进算法O(nlogn)

最大连续子序列和的问题还可以用分治法解决。假设输入的整数序列是{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节介绍递归函数时间复杂度的计算。