问题引入： 在一串整数数列的一维方向上找到一个连续的子序列使其和最大。为方便起见，如果数列中含有负数，最大子序列和最小为 0 。
求解这个问题的算法有很多种，本文将要分析穷举法，分治法和联机算法三种算法的优劣。理论上来讲，一个算法的复杂性越低，算法的运行效率越高，当然除了算法本身外，还有一些外部的因素也会影响算法是否合适，比如说只需要少量的输入，那就没有必要花费大把精力去研究精巧的算法，但如果大量输入，想要提高运行速率，好的算法还是非常有必要的。
算法一 穷举法
这个算法实现起来较简单，只要穷举所有的可能，最后得出最大子序列和。具体做法就是先列出子序列第一个数的位置，然后枚举后面的元素并求和，和前一个和比较大小，保留较大的值，知道最后一个。依次循环，直到穷举完所有的子序列。
先看看算法是怎样实现的。
int MaxSubsequenceSum(const int A[], int N) {
int ThisSum,MaxSum,i,j;
/* 对 i 进行遍历 */
MaxSum = 0;
for( i = 0; i < N; i++ ) {
ThisSum = 0;
/* 遍历以 A[i] 开头的所有可能的子序列 */
for( j = i; j < N; j++ ) {
ThisSum += A[j];
if( ThisSum > MaxSum )
MaxSum = ThisSum;
}
}
return MaxSum;
}
这个算法中两个 for 循环穷举出了所有可能，复杂度为 O(N^2) ，效率不算太高，但对处理少量的数据基本上够用了。
算法二 分治法
这个算法实现起来相对复杂一点，和上一个算法一致，也是用了递归的方法。
先说说什么是分治的思想，“分”就是把问题分成两个大致相等的子问题，“治”就是将两个子问题的解合并到一起并可能做一点附加工作，最后的到整个问题的解。
在这个问题中，最大子序列可以有三种情况：整个出现在左半段或右半段，或者分布在左右两个部分。前两种情况递归求解即可，第三种情况可以分别求出前半段的最大和（包含最后一个元素），后半段的最大和（包含第一个元素），然后相加而得到。
同样的来看看具体算法是怎样实现的。
static int
MaxSubSum( const int A[],int Left,int Right )
{
int MaxLeftSum,MaxRightSum; //声明左右两边的最大子序列
int MaxLeftBorderSum,MaxRightBorderSum; //声明左右两边包含靠中间边界元素的醉的子序列
int LeftBorderSum,RightBorderSum; //声明左右两边子序列的和
int Center,i;
/* 处理基准情况，即在这里指只有一个元素 */
if( Left == Right )
if( A[Left] > 0 )
return A[Left];
else
return 0;
Center = (Left + Right)/2; //不用考虑奇偶的原因是C语言会自动向下取整
MaxLeftSum = MaxSubSum(A,Left,Center); //递归调用，分出左边元素
MaxRightSum = MaxSubSum(A,Center+1,Right); //递归调用，分出右边元素
/* 求左边包含最后一个元素的最大子序列 */
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for( i = Center; i >= Left; i-- )
{
LeftBorderSum += A[i];
if( LeftBorderSum > MaxLeftBorderSum )
MaxLeftBorderSum = LeftBorderSum;
}
/* 求右边包含第一个元素的的最大子序列 */
MaxRightBorderSum = 0;
RightBorderSum = 0;
for( i = Center + 1; i <= Right; i++ )
{
RightBorderSum += A[i];
if( RightBorderSum > MaxRightBorderSum )
MaxRightBorderSum = RightBorderSum;
}
/* 返回三种情况的最大值，这里调用了外部函数，并且包含隐式函数声明，需慎用 */
return Max3( MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum );
}
/* 求 3 个数的最大值 */
int Max3(long a,long b,long c)
{
if( a < b )
{
a = b;
}
if( a > c )
return a;
else
return c;
}
int
MaxSubsequenceSum( const int A[],int N )
{
return MaxSubSum( A,0,N - 1);
}
这个算法的复杂度是 O(N log N) ，具体分析过程尚未理解，待日后理解再加补充。
算法三 联机算法
联机算法具有的特性： 只对数据进行一次扫描，一旦读入就不需要再记忆。在任意时刻都能把它已经读入的数据给出子序列的正确答案。
本算法中有一个重要的思想，即当 A[i] 为负数的时候，是不可能为最大子序列的起点的，下面我们来看看实现过程。
int
MaxSubsequenceSum( const int A[],int N )
{
int ThisSum,MaxSum,j;
ThisSum = MaxSum = 0;
for( j = 0;j < N;j++ )
{
ThisSum += A[j];
if( ThisSum > MaxSum )
MaxSum = ThisSum;
else if( ThisSum < 0 )
ThisSum = 0;
}
return MaxSum;
}
这是一个常量空间并以线性时间运行的算法，其复杂度是 O(N) ，运行效率颇高，是超大量数据分析的较佳算法。
这个算法用特值代替比较简单，但要理解为什么正确可能需要费点时间。
这个算法可以和算法一相类比，算法一中 i 代表当前序列的起点，j 代表终点。如果我们不需要知道最佳子序列的位置，那么 i 也就没有了存在的必要。
由于 A[i] 不能为负数，所以在循环中，如果我们检测到了从 A[i] 到 A[j] 的子序列是负数的时候，我们就可以向前推进 i ，类似的任何负的子序列都不可能是最佳子序列的前缀。例如说循环中我们检测到从 A[i] 到 A[j] 的子序列是负数那么我们就可以推进 i ，从 i+1, i+2, i+3 一直推进到 j+1。j 是使得从下标i开始成为负数的第一个下标,因此这样看来我们的 i 就可以消掉了。
注意的是，虽然，如果有以 A[j] 结尾的某序列和是负数就表明了这个序列中的任何一个数不可能是与 A[j] 后面的数形成的最大子序列的开头，但是并不表明 A[j] 前面的某个序列就不是最大序列，也就是说不能确定最大子序列在 A[j] 前还是 A[j] 后，即最大子序列位置不能求出。但是能确保 MaxSum 的值是当前最大的子序列和。
可以编译运行的程序，其他算法需要编译直接替换了就好，主函数部分不用修改。
# include<stdio.h>
int MaxSubsequenceSum(const int A[],int N);
int main()
{
int A[] = {-2,11,-4,13,-5,-2},N;
N = sizeof(A)/sizeof(A[0]);
MaxSubsequenceSum(A,N);
printf("length = %d \n",N);
printf("the sum of the maxsubsequence is %d \n",MaxSubsequenceSum(A,N));
return 0;
}
/* 后面的内容可以替换 */
int
MaxSubsequenceSum( const int A[],int N )
{
int ThisSum,MaxSum,j;
ThisSum = MaxSum = 0;
for( j = 0;j < N;j++ )
{
ThisSum += A[j];
if( ThisSum > MaxSum )
MaxSum = ThisSum;
else if( ThisSum < 0 )
ThisSum = 0;
}
return MaxSum;
}
