最大子序列和问题

时间:2022-10-16 00:44:46

一串数据,可能有负数,求和最大的子序列,如果所有数据为负,返回0

O(N^2)

 1 // 暴力求解
 2 
 3 int maxsubseq(const int* a, int n)
 4 {
 5   int maxsum = 0;
 6   for(int i = 0; i < n; i++)
 7    {
 8      int tmpsum = 0;
 9         for(int j = i; j < n; j++)
10         {
11           int tmpsum += a[j];
12            if(tmpsum > maxsum)
13               maxsum = tmpsum;      
14         }
15   }
16   return maxsum;
17 }

O(N*logN)

分治思想:吧问题分成两个大致相等的子问题,然后递归地对他们求解

T(n)=2T(n/2)+O(n)

 1 //最大子序列可能整个出现在数据的左半、右半,或者出现在中部从而占据左右两半的部分
 2 static int
 3 Max3( int A, int B, int C )
 4 {
 5  return A > B ? A > C ? A : C : B > C ? B : C;
 6 }
 7  
 8 
 9 static int
10 MaxSubSum( const int A[ ], int Left, int Right )
11 {
12   int MaxLeftSum, MaxRightSum;
13   int MaxLeftBorderSum, MaxRightBorderSum;
14   int LeftBorderSum, RightBorderSum;
15   int Center, i;
16  
17   if( Left == Right )  /* Base case */
18     if( A[ Left ] > 0 )
19          return A[ Left ];
20        else
21          return 0;
22  
23   Center = ( Left + Right ) / 2;
24   MaxLeftSum = MaxSubSum( A, Left, Center );
25   MaxRightSum = MaxSubSum( A, Center + 1, Right );
26  
27   MaxLeftBorderSum = 0; LeftBorderSum = 0;
28   for( i = Center; i >= Left; i-- )
29    {
30     LeftBorderSum += A[ i ];
31     if( LeftBorderSum > MaxLeftBorderSum )
32          MaxLeftBorderSum = LeftBorderSum;
33    }
34  
35   MaxRightBorderSum = 0; RightBorderSum = 0;
36   for( i = Center + 1; i <= Right; i++ )
37    {
38     RightBorderSum += A[ i ];
39        if( RightBorderSum > MaxRightBorderSum )
40          MaxRightBorderSum = RightBorderSum;
41    }
42  
43   return Max3( MaxLeftSum, MaxRightSum,
44             MaxLeftBorderSum + MaxRightBorderSum );
45 }

 O(N):联机算法

int maxsubseq(const int* a, int n)
{
    int tmpsum, maxsum, j;
    tmpsum = maxsum = 0;
    for(j = 0; j < N; j++)
    {
        tmpsum += a[j];
        if(tmpsum > maxsum)
            maxsum = tmpsum;
        else if(tmpsum < 0)
            tmp = 0;
    }
    return maxsum;
}

联机算法只对数据进行一次扫描,一旦a[j]被读入并被处理,它就不再需要被记忆。在任意时刻,算法都能对已经读入的数据给出子序列和问题的正确答案,具有这种特性的算法叫做联机算法(online algorithm)