本文共 2235 字，大约阅读时间需要 7 分钟。

                                                      求解最大子序列和

        记录下最大序列和的多个实现方法，时间复杂度由高至低，分别为ON3、ON2、ONlogN、ON。分别对应的是：直接穷举式、穷举改进式、分治处理、联机算法。好的算法实现，总给人以美的体验。

        下面直接贴代码：

#include 
   
    int MaxSubsequenceSum1(const int *PArr,int n){    int ThisSum, MaxSum, i, j, k;    MaxSum=0;    for(i=0; i< n; i++)    {        for(j= i;j< n; j++)        {            ThisSum= 0;            for(k= i;k<= j;k++)            {                ThisSum += PArr[k];            }            if(ThisSum > MaxSum)            {                MaxSum= ThisSum;            }        }    }    return MaxSum;    }int MaxSubsequenceSum2(const int *PArr,int n){	int ThisSum, MaxSum, i, j;		MaxSum=0;	for(i=0; i< n; i++)	{		ThisSum= 0;		for(j= i;j< n; j++)		{			ThisSum += PArr[j];						if(ThisSum > MaxSum)			{				MaxSum= ThisSum;			}		}	}	return MaxSum;}int Max3(int a, int b, int c){	return (a >= b)?((a >= c)?(a):(c)):((b >= c)?(b):(c));}static int MaxSubSum(const int *PArr,int Left,int Right){	int MaxLeftSum, MaxRightSum;	int MaxLeftBorderSum, MaxRightBorderSum;	int LeftBorderSum, RightBorderSum;	int Center, i;	if(Left == Right)		if(PArr[Left] > 0)			return PArr[Left];		else			return 0;		Center= (Left + Right)/2;	MaxLeftSum= MaxSubSum(PArr, Left, Center);	MaxRightSum= MaxSubSum(PArr, Center+1, Right);		MaxLeftBorderSum= 0;	LeftBorderSum= 0;	for(i = Center; i >= Left; i--)	{		LeftBorderSum += PArr[i];		if(LeftBorderSum > MaxLeftBorderSum)			MaxLeftBorderSum= LeftBorderSum;	}		MaxRightBorderSum= 0;	RightBorderSum= 0;	for(i= Center + 1; i <= Right; i++)	{		RightBorderSum += PArr[i];		if(RightBorderSum > MaxRightBorderSum)			MaxRightBorderSum= RightBorderSum;	}	return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);}int MaxSubsequenceSum3(const int *PArr,int n){	return MaxSubSum(PArr, 0, n-1);}int MaxSubsequenceSum4(const int *PArr,int n){	int ThisSum, MaxSum, j;		ThisSum= MaxSum= 0;	for(j= 0; j< n; j++)	{		ThisSum += PArr[j];				if(ThisSum > MaxSum)			MaxSum= ThisSum;		else if(ThisSum < 0)			ThisSum= 0;	}	return MaxSum;}int main(void) {     int testArr[10]= {1,3,5,7,-9,-5,4,8,10,0};	printf("%d\n",MaxSubsequenceSum1(testArr,10));	printf("%d\n",MaxSubsequenceSum2(testArr,10));	printf("%d\n",MaxSubsequenceSum3(testArr,10));	printf("%d\n",MaxSubsequenceSum4(testArr,10));	return 0;}
   

转载地址：http://pemsi.baihongyu.com/