【算法】最大子序列和问题

转载自http://www.2cto.com/database/201412/365548.html

问题描述：

输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：

序列：-2 11 -4 13 -5 -2，则最大子序列和为20。

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。

下面依次给出几个不同实现算法

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

int MaxSubseqSum1( int A[], int N )//算法1  T( N ) = O( N3 ) { int ThisSum, MaxSum = 0; int i, j, k; for ( i = 0; i < N; i++ )   { for ( j = i; j < N; j++ )   { ThisSum = 0; for ( k = i; k <= j; k++ ) ThisSum += A[k]; if( ThisSum > MaxSum ) MaxSum = ThisSum; } } return MaxSum; } int MaxSubseqSum2( int A[], int N )  //算法2T( N ) = O( N2 ) { int ThisSum, MaxSum = 0; int i, j; for ( i = 0; i < N; i++ )   { ThisSum = 0; for ( j = i; j < N; j++ )   { ThisSum += A[j]; if( ThisSum > MaxSum ) MaxSum = ThisSum; } } return MaxSum; } int MaxSubseqSum4( int A[], int N ) //算法4T( N ) = O( N2 ) { int ThisSum, MaxSum; int i; ThisSum = MaxSum = 0; for ( i = 0; i < N; i++ ) { ThisSum += A[i]; if( ThisSum > MaxSum ) MaxSum = ThisSum; else if( ThisSum < 0 ) ThisSum = 0; } return MaxSum; }//“在线”的意思是指每输入一个数据就进行即时处理，在任 何一个地方中止输入，算法都能正确给出当前的解。

算法3---分治法