【算法】最大子序列和問題

轉載自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---分治法