算法进化历程之“最大连续子序列之和”.doc
文本预览下载声明
算法进化历程之“最大连续子序列之和”
巧若拙（欢迎转载，但请注明出处： HYPERLINK /qiaoruozhuo \t _blank /qiaoruozhuo）
题目描述：
给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 = i = j = K。最大连续子序列是所有连续子序列中元素和最大的一个， 例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。
输入：
测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。
输出：
对每个测试用例，在1行里输出最大和。若所有K个元素都是负数，则定义其最大和为0。
输入示例：
6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0
输出示例：
20
10
10
10
0
0
算法分析：
算法1：
最直接的想法是蛮力穷举。计算每一段可能的连续子序列A[i..j]之和，然后保留最大值。由于有三层循环，故时间复杂度为O(N^3)。代码如下：
int MaxSubsequenceSum_1(const int A[], int n)//低效算法1
{
int sum, maxSum, i, j, k;
maxSum = 0;
for (i=0; in; i++)
{
for (j=i; jn; j++)
{
sum = 0;
for (k=i; k=j; k++)//计算连续子序列A[i..j]之和
{
sum += A[k];
}
if (sum maxSum)
maxSum = sum;
}
}
return maxSum;
}
算法2：
仔细观察算法1，我们发现其实最内层循环是不必要的，因为我们可以直接在最外层循环中设置sum = 0;然后累计每一个A[j]值就可以得到A[i..j]之和了。由于只有两层循环，故时间复杂度为O(N^2)。代码如下：
int MaxSubsequenceSum_2(const int A[], int n)//低效算法2
{
int sum, maxSum, i, j, k;
maxSum = 0;
for (i=0; in; i++)
{
sum = 0;
for (j=i; jn; j++)
{
sum += A[j];
if (sum maxSum)
maxSum = sum;
}
}
return maxSum;
}
算法3：
虽然算法2把时间复杂度减小到O(N^2)，但还算不上高效的算法，我们可以采用一种“分治”策略，把序列分成左右两个部分，则最大子序列和可能在三处出现：左半部，右半部，或者跨越数据的中部而占据左右两半部分。前面两种情况可以递归求解，第三种情况需要计算出左半部最大和（必须包含左半部最右元素）以及右半部最大和（必须包含右半部最左元素），然后将这两个和加在一起。最后返回三者的最大值。
由于采用了分治算法，所以时间复杂度可以减小到O(NlogN)。
代码如下：
int MaxSubsequenceSum_3(const int A[], int n)//分治算法
{
return MaxSubSum(A, 0, n-1);
}
int MaxSubSum(const int A[], int left, int right)//分治算法子程序
{
int maxLeftSum, maxRightSum;
int maxLeftBorderSum, maxRightBorderSum;
int leftBorderSum, rightBorderSum;
int mid, i;
if (left == right)
return (A[left] 0) ? A[left] : 0;
mid = (left + right) / 2;
maxLeftSum = MaxSubSum(A, left, mid); //递归计算左半部子序列最大和
maxRightSum = MaxSubSum(A, mid+1, right);//递归计算右半部子序列最大和
maxLeftBorderSum = leftBorderSum = 0;
for (i=mid;
显示全部