您所在位置：主题：数据结构与算法分析—C语言描述（Mark Alen Weiss)中的一个问题
superflytiger
[专家分：0] 发布于 2008-03-07 18:47:00
这是求最大子序列的一个递归实现，使用分治算法。比如
4 -3 5 -2 -1 2 6 -2 的最大子序列的和为11。（书中第20页）
书上说第9到17行之间花费的时间为O(N)。但我觉得好像是O（N^2）。想不出为什么会是O（N）。
请高手指点一下。
static int
Max3( int A, int B, int C )
{
return A > B ? A > C ? A : C : B > C ? B : C;
}
/* START: fig2_7.txt */
static int
MaxSubSum( const int A[ ], int Left, int Right )
{
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int Center, i;
/* 1*/ if( Left == Right ) /* Base case */
/* 2*/ if( A[ Left ] > 0 )
/* 3*/ return A[ Left ];
else
/* 4*/ return 0;
/* 5*/ Center = ( Left + Right ) / 2;
/* 6*/ MaxLeftSum = MaxSubSum( A, Left, Center );
/* 7*/ MaxRightSum = MaxSubSum( A, Center + 1, Right );
/* 8*/ MaxLeftBorderSum = 0; LeftBorderSum = 0;
/* 9*/ for( i = Center; i >= Left; i-- )
{
/*10*/ LeftBorderSum += A[ i ];
/*11*/ if( LeftBorderSum > MaxLeftBorderSum )
/*12*/ MaxLeftBorderSum = LeftBorderSum;
}
/*13*/ MaxRightBorderSum = 0; RightBorderSum = 0;
/*14*/ for( i = Center + 1; i <= Right; i++ )
{
/*15*/ RightBorderSum += A[ i ];
/*16*/ if( RightBorderSum > MaxRightBorderSum )
/*17*/ MaxRightBorderSum = RightBorderSum;
}
/*18*/ return Max3( MaxLeftSum, MaxRightSum,
/*19*/ MaxLeftBorderSum + MaxRightBorderSum );
}
int
MaxSubsequenceSum( const int A[ ], int N )
Aug 12 15:27 1996 max_sum.c Page 3
{
return MaxSubSum( A, 0, N - 1 );
}
/* END */
