给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。
“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
很容易想到一种最暴力的方式，那就是逐个逐个的累计，从i=0到i=N,总共需要N次大循环，并且对每次大循环里又分别进行逐项相加并且判断最大值 先给出时间复杂度为O(N^2)的算法算法一
#include
#include
int MaxSubseqSum( int A[], int N );
int main()
{
int k,i,A[100000],maxsum;
scanf("%d",&k);
for(i=0;i<k;i++)
scanf("%d",&A[i]);
maxsum=MaxSubseqSum(A,k);
printf("最大子列之和是%d\n",maxsum);
return 0;
}
int MaxSubseqSum( int A[], int N ) {
int ThisSum, MaxSum = 0;
int i, j;
for( i = 0; i < N; i++ )
{
/* i是子列左端位置 */
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( j = i; j < N; j++ ) { /* j是子列右端位置 */
ThisSum += A[j];/*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/
if( ThisSum > MaxSum )/* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j 循环结束 */
}
/* i循环结束 */
return MaxSum;
}
对以上算法进行优化，关键在于，如果累加的和已经开始小于0，那么就把前面的值都抛弃掉，重新计算最大值。
算法二：
#include
#include
int main()
{
int k,i,sum,maxint;
scanf("%d",&k);
int *p=(int *)malloc(k*sizeof(int));//内存动态分配
sum=maxint=0;
for(i=0;i<k;i++)
scanf("%d",p+i);
for(i=0;i<k;i++) { //不断将得到的sum和已存的maxint比较，maxint存的始终是较大的值
sum+=p[i];
if(maxint<sum)
maxint=sum;
else if(sum<0)//如果值开始小于0，那么下一项无论加什么值都会让sum变小，所以舍弃
sum=0;
}
printf("最大子列之和是%d\n",maxint);
free(p);//释放空间
return 0;
}
算法二用到了在线处理的思想，时间复杂度为O(N)。已经是最优算法，因为无论怎么写，总要遍历一遍。可以看到，算法二的效率比算法一快很多