最大子序列和问题

最大子序列和问题：给定整数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 }

秒客网

最大子序列和问题

相关文章