2.4.3最大子序列和问题的解
最大的子序列和问题：给定整数A1，A2，……，AN（可能有负数），求∑(k=i)^j A_k 的最大值（为方便起见，如果所有整数均为负数，则最大子序列和为0）
• 算法3
//T(N)=O(N log N)
static int MaxSubSum( const int A[], int Left,int Right )
{
int MaxLeftSum,MaxRightSum;
int MaxLeftBorderSum,MaxRightBorderSum;
int LeftBorderSum,RightBorderSum;
int Center,i;
if(Left==Right) //Base Case,即'基准情形'
if (A[Left]>0)
return A[Left];
else
return 0;
Center = (Left + Right)/2;
MaxLeftSum=MaxSubSum(A,Left,Center);//左边中最大的子序列和
MaxRightSum=MaxSubSum(A,Center+1,Right);//右边中最大的子序列和
MaxLeftBorderSum = 0; LeftBorderSum = 0;
for(i=Center;i>=Left;i--)//从中心开始向左找最大子序列和
{
LeftBorderSum+=A[i];
if(LeftBorderSum>MaxLeftBorderSum)
MaxLeftBorderSum= LeftBorderSum;
}
MaxRightBorderSum = 0; RightBorderSum = 0;
for(i=Center+1;i<=Right;i+ +)//从中心开始向右找最大子序列和
{
RightBorderSum+=A[i];
if(RightBorderSum>MaxRightBorderSum)
MaxRightBorderSum=RightBorderSum;
}
return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum);
}
int MaxSubsequenceSum(const int A[], int N)
{
return MaxSubSum(A , 0 , N - 1);
}
int Max3(int a,int b,int c)
{
if (a>b)
if (a>c) return a;
else return c;
else
if (c>b) return c;
else return b;
}
• 更简单有效的算法4
int MaxSubsequenceSum(const int A[], int N)
{
int ThisSum,MaxSum,j;
ThisSum=MaxSum=0;
for(j=0;j<N;j++)
{
ThisSum+=A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0) //这一步是关键，如果前j项和是负的，那就可以扔掉不要了
ThisSum=0;
}
return MaxSum;
}
这种算法的附带优点是，只需要扫描一次数据，一旦A[i]被扫入并被处理，它就不再需要被记忆【5/13:数据赋值等操作少】。在任何时刻，算法都能对它已经读入的数据给出子序列问题的正确答案（其他算法不具有这个特性）【5/13:也就是说，假如你输入的是10个数据，在你输入到任何一个的时候，在这种情况下的解已经被算出来了】。具有这种特性的算法叫做联机算法（online algorithm）。
2.4.4运行时间中的对数
除分治算法外，可将对数最常出现的规律概括为下列一般法则：如果一个算法用常数时间（O（1））将问题的大小削减为其一部分（通常是1/2），那么该算法就是O（log N）。另一方面，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是O（N）的。 【5/15:可以理解为就是一个循环中，如果这个算法本身能够自己削减循环次数的话，那么就会从O（N）降到O（log N）】
• 对分算法
//T(N)=O（log N）
int BinarySearch(const int A[], int x,int n)
{
int Low,Mid,High;
Low=0;High=n-1;
while(Low <= High)
{
Mid = (Low+High) /2;
if(A[Mid]<x)
Low=Mid+1;
else if(A[Mid]> x)
High=Mid-1;
else
return Mid;
}
return NotFound;
}
它提供了在O（log N）时间内的Find（查找）操作。访问次数少，而如果是顺序查找的话就会需要多很多的访问次数。 • 欧几里德算法
unsigned int Gcd(unsigned int M,unsigned int N)
{
unsigned int Rem;
while( N>0 )
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}
定理2.1：如果M > N , 则M mod N < M/2。T（N）=O（log N） 。 • 幂运算
//T(N)=O(log N)
long int Pow(int X,unsigned int N)
{
if( N == 0 )
return 1;
if( N == 1 ) /**接下来的两行也可以不写**/
return X;
if( IsEven( N ) )
return Pow( X * X, N / 2 );
/**
以下的修改都是不可取的:
return Pow( Pow( X, 2), N / 2);
return Pow( Pow( X, N / 2), 2);
-以上这两种会产生无限循环，导致程序崩溃
return Pow( X, N / 2)* Pow(X, N / 2 );
-这种影响程序的效率【运行时间应该是O（N）(?)】
**/
else
return Pow( X * X, N / 2 ) * N;
/**
如果不写N==1那两行的话，上面这行还可以写成
return Pow(X,N-1)*X;
**/
}
“有时候看一看程序能够进行多大的调整而不影响其正确性倒是很有意思的”
