求解最大连续子序列和问题
【问题描述】给定一个有n（n>=1）个整数的序列，求出其中最大连续子序列的和。例如序列（-2,，11，-4,13，-5，-2）的最大子序列和为20，序列（-6,2,4，-7,5,3,2，-1,6，-9,10，-2）的最大子序列和为16。规定一个序列的最大连续子序列和至少是0，如果小于0，其结果为0。
【问题求解】 最大连续子序列只可能出现在3个地方： 第一种：该子序列完全落在左半部分，即a[0...mid]中，采用递归求出其最大连续子序列和maxLeftSum 第二种：该子序列完全落在右半部分，即a[mid+1...right]中，采用递归求出其最大连续子序列和maxRightSum 第三种：该子序列跨越序列a的中部而占据左、右两部分。
源程序如下：
#include <iostream> #include <algorithm> using namespace std; //求解最大连续子序列和问题 long maxSubSum(int a[],int left,int right) { int i, j; long maxLeftSum, maxRightSum; long maxLeftBorderSum, leftBorderSum; long maxRightBorderSum, rightBorderSum; if (left==right) { //当子序列只有一个元素时,递归出口 if (a[left]>0) { return a[left]; //该元素大于0时返回它 } else { return 0; //该元素小于或者等于0时，返回0 } } int mid = (left + right) / 2; //求中间位置 maxLeftSum= maxSubSum(a,left,mid); //求左边的最大连续子序列之和 maxRightSum=maxSubSum(a, mid +1,right); //求右边的最大连续子序列之和 maxLeftBorderSum = 0; leftBorderSum = 0; for (i = mid; i >= left;i--) { //求出以左边加上a[mid]元素构成的序列的最大和 leftBorderSum += a[i]; if (leftBorderSum> maxLeftBorderSum) { maxLeftBorderSum = leftBorderSum; } } maxRightBorderSum = 0; rightBorderSum=0; for (j = mid+1; j <= right; j++) { //求出以左边加上a[mid]元素构成的序列的最大和 rightBorderSum += a[j]; if (rightBorderSum > maxRightBorderSum) { maxRightBorderSum = rightBorderSum; } } //返回三者之中的最大值 return max(max(maxLeftSum, maxRightSum), maxLeftBorderSum+ maxRightBorderSum); } int main() { int n = 0; cout << "请输入数组元素的个数" << endl; cin >> n; int *a = new int[n]; cout << "请输入数组的元素" << endl; for (int i = 0; i < n;i++) { cin >> a[i]; } cout << "最大连续子序列的和为：" << maxSubSum(a, 0, n - 1) << endl; system("pause"); return 0; }输出结果：
请输入数组元素的个数 6 请输入数组的元素 -2 11 -4 13 -5 -2 最大连续子序列的和为：20 请按任意键继续. . .
【算法分析】设求解序列a[0..n-1]最大连续子序列和的执行时间为T(n),第（1）（2）种情况的执行时间为T（n/2）,第（3）中情况的执行时间为O（n）,所以得到以下递推式：
T(n)=1; 当n=1时
T(n)=2T(n/2)+n 当n>1时
容易推出T(n)=O(nlog2n)
