算法一，暴力法惫周，時間復雜度O(n^3):
int MaxSubseqSum1( int A[], int N )
{ int ThisSum, MaxSum = 0;
int i, j, k;
for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
for( j = i; j < N; j++ ) { /* j是子列右端位置 */
ThisSum = 0; /* ThisSum是從A[i]到A[j]的子列和 */
for( k = i; k <= j; k++ )
ThisSum += A[k];
if( ThisSum > MaxSum ) /* 如果剛得到的這個子列和更大 */
MaxSum = ThisSum; /* 則更新結(jié)果 */
} /* j循環(huán)結(jié)束 */
} /* i循環(huán)結(jié)束 */
return MaxSum;
}
算法二尘惧，時間復雜度O(n^2):
int MaxSubseqSum2( 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次循環(huán)的基礎上累加1項即可*/
if( ThisSum > MaxSum ) /* 如果剛得到的這個子列和更大 */
MaxSum = ThisSum; /* 則更新結(jié)果 */
} /* j循環(huán)結(jié)束 */
} /* i循環(huán)結(jié)束 */
return MaxSum;
}
算法三褥伴，在線處理，時間復雜度O(n)：
int MaxSubseqSum4( int A[], int N )
{ int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for( i = 0; i < N; i++ ) {
ThisSum += A[i]; /* 向右累加 */
if( ThisSum > MaxSum )
MaxSum = ThisSum; /* 發(fā)現(xiàn)更大和則更新當前結(jié)果 */
else if( ThisSum < 0 ) /* 如果當前子列和為負 */
ThisSum = 0; /* 則不可能使后面的部分和增大漾狼，拋棄之 */
}
return MaxSum;
}
算法四重慢，分治法，時間復雜度O(nlogn).
