分治法求最大子段与首先将问题.docVIP

分治法求最大子段和首先将问题 1、基本思想： 用分治法求最大子段和首先将问题划分，即将一直序列划分成长度相等的两个序列，这时会出现3种情况，即 eq \o\ac(○,1)最大子段和在第一个序列， eq \o\ac(○,2)最大子段和在第二个序列和 eq \o\ac(○,3)最大子段和在第一个序列与第二个序列之间。然后，将3种情况的最大子段和合并，取三者之中的最大值为问题的解。 2、复杂度分析： 对应划分得到的情况 eq \o\ac(○,1)和 eq \o\ac(○,2)，需要分别递归求解，对应情况 eq \o\ac(○,3)，两个并列的for循环的时间复杂度是O(n)，所以有递推公式为： 1 n=1 T(n)= 2T(n/2)+n n1 所以，分治算法的时间复杂度是O(nlog2n)。 3、代码实现： #include IOSTREAM #include TIME.H #include WINDOWS.H #define MAX 10000 using namespace std; int fzhsum(int a[],int left,int right)//分治法 { int sum=0; int leftsum=0,rightsum=0; int center; int i; if(left==right) { if(a[left]0) sum=a[left]; else sum=0; } else { center=(left+right)/2; leftsum=fzhsum(a,left,center); rightsum=fzhsum(a,center+1,right); int s1=0,lefts=0; for(i=center;i=left;i--) { lefts+=a[i]; if(lefts=s1) s1=lefts; } int s2=0,rights=0; for(i=center+1;i=right;i++) { rights+=a[i]; if(rights=s2) s2=rights; } sum=s1+s2; if(sumleftsum) sum=leftsum; if(sumrightsum) sum=rightsum; } return sum; } void main() { int num[MAX]; int i; int n; int index1,index2; LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(frequency); cout输入整数序列大小：;//生成随机序列 cinn; cout产生的随机序列为：; srand(time(0)); for (i=0;in;i++) { if(rand()%2==0) num[i]=rand()%1000; else num[i]=(-1)*rand()%1000; coutnum[i] ; } cout分治法求最大子段和为:;//分治法 //cout最大子段和:; QueryPerformanceCounter(begin); coutfzhsum(num,0,n)endl; QueryPerformanceCounter(end); cout最大子段:; cout从num[index1]到num[index2]endl; cout求解时间（单位：s）:(double)(end.QuadPart-begin.QuadPart) /frequency.QuadPartendl; }