最大子序列和问题

最大子序列和问题：给定整数A1, A2, ..., An(可能有负数)，ΣAk的最大值(为方便起见，如果所有整数均为负数，则最大子序列和为0)。

      例：输入-2，11，-4，13，-5，-2时，答案为20(从A2到A4)。

 

算法1：穷举所有可能，立方运行时间。

 1 int MaxSubsequenceSum( const int A[ ], int N )
 2 {
 3     int ThisSum, MaxSum, i, j, k;
 4 
 5     MaxSum = 0;
 6     for( i = 0; i < N; i++ )
 7         for( j = i; j < N; j++ )
 8         {
 9             ThisSum = 0;
10             for( k = i; k <= j; k++ )
11                 ThisSum += A[ k ];
12 
13             if( ThisSum > MaxSum )
14                 MaxSum = ThisSum;
15         }
16         return MaxSum;
17 }

算法2： 平方运行时间。

 1 int MaxSubsequenceSum( const int A[ ], int N )
 2 {
 3     int ThisSum, MaxSum, i, j;
 4 
 5     MaxSum = 0;
 6     for( i = 0; i < N; i++ )
 7     {
 8         ThisSum = 0;
 9         for( j = i; j < N; j++ )
10         {
11             ThisSum += A[ j ];
12 
13             if( ThisSum > MaxSum )
14                 MaxSum = ThisSum;
15         }
16     }
17     return MaxSum;
18 }

算法3：分治策略，NlogN运行时间。

 1 static int Max3( int A, int B, int C )
 2 {
 3     return A > B ? A > C ? A : C : B > C ? B : C;
 4 }
 5 
 6 static int MaxSubSum( const int A[ ], int Left, int Right )
 7 {
 8     int MaxLeftSum, MaxRightSum;
 9     int MaxLeftBorderSum, MaxRightBorderSum;
10     int LeftBorderSum, RightBorderSum;
11     int Center, i;
12 
13     if( Left == Right ) /* Base case */
14         if( A[ Left ] > 0 )
15             return A[ Left ];
16         else
17             return 0;
18 
19     Center = ( Left + Right ) / 2;
20     MaxLeftSum = MaxSubSum( A, Left, Center );
21     MaxRightSum = MaxSubSum( A, Center + 1, Right );
22 
23     MaxLeftBorderSum = 0; LeftBorderSum = 0;
24     for( i = Center; i >= Left; i-- )
25     {
26         LeftBorderSum += A[ i ];
27         if( LeftBorderSum > MaxLeftBorderSum )
28             MaxLeftBorderSum = LeftBorderSum;
29     }
30 
31     MaxRightBorderSum = 0; RightBorderSum = 0;
32     for( i = Center + 1; i <= Right; i++ )
33     {
34         RightBorderSum += A[ i ];
35         if( RightBorderSum > MaxRightBorderSum )
36             MaxRightBorderSum = RightBorderSum;
37     }
38 
39     return Max3( MaxLeftSum, MaxRightSum,
40         MaxLeftBorderSum + MaxRightBorderSum );
41 }
42 
43 int MaxSubsequenceSum( const int A[ ], int N )
44 {
45     return MaxSubSum( A, 0, N - 1 );
46 }

算法4：线性运行时间。

 1 int MaxSubsequenceSum( const int A[ ], int N )
 2 {
 3     int ThisSum, MaxSum, j;
 4 
 5     ThisSum = MaxSum = 0;
 6     for( j = 0; j < N; j++ )
 7     {
 8         ThisSum += A[ j ];
 9 
10         if( ThisSum > MaxSum )
11             MaxSum = ThisSum;
12         else if( ThisSum < 0 )
13             ThisSum = 0;
14     }
15     return MaxSum;
16 }

算法5：修改算法4增加最大子序列和的子序列起始位置和终止位置。

 1 int MaxSubsequenceSum( const int A[], int N, int& x, int& y )
 2 {
 3     int ThisSum, MaxSum, t, j;
 4 
 5     t = 0;
 6     ThisSum = MaxSum = 0;
 7     for( j = 0; j < N; j++ )
 8     {
 9         ThisSum += A[j];
10         if( ThisSum > MaxSum )
11         {
12             MaxSum = ThisSum;
13             y = j;
14         }else if( ThisSum < 0 )
15         {
16             ThisSum = 0;
17             t = j + 1;
18         }
19         if ( t <= y )
20             x = t;
21     }
22     return MaxSum;
23 }
24 
25 int main()
26 {
27     int x = 0, y = 0;
28     int A[] = {4, -3, 5, -2, -1, 2, 6, -12};
29 
30     int r = MaxSubsequenceSum(A, sizeof(A)/sizeof(A[0]), x, y);
31     printf("%d, %d, %d\n", r, x+1, y+1);
32 
33     return 0;
34 }
轉自：http://www.cnblogs.com/shengjin/archive/2010/01/08/1641975.html