递归与分治策略解决最大字段和问题

《递归与分治策略解决最大字段和问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、递归与分治策略…最大子段和问题1、问题的描述给定由n个整数组成的序列（al,a2,…,an）,求该序列形如g的子段和的最大值。分治算法就是将一个问题分解成若干个小问题，对若干个小问题分别求解，最后在合并起来。最大子段问题可以分成三种情况1.数组a[l-n]（BP数组前1至n个元素）的最大子段和a[l・n/2]的最大子段相同2数组a[l-n]（W数组前1至n个元素）的最大子段和a[n/2+l-n]的最大子段相同3.数组a[l-n]的最大子段和是由a[l-n/2]和a[n/2+l・n]结合而成，求解方法为则分别求出n/2imaxSa[k]和

2、maxSa[k],然后将两个值相加即得到此种情况下的数组最大子段和0<二iv二n/2k=in/2+l<=iv二nk二n/2最后分别求出三种情况的最大子段和，再比较三个子段和，最大的那个即为数组的最大字段和。2、代码及注释^include^include#include#defineMAX_N20intmax3(int,int,int):intmaxSubArrayAr)s(int[]);intmaxSubArrtiy(ini[],int,int);intmain()intnums[M

3、AX_N]；//定义一个最大长度为20的数组inti;stand(time(0));//随机数产生器printf("array:");//产生MAXN个随机数for(i=0;i

4、intmax3(inta,intb,intc){if(a>b)returna>c?a:c;elsereturnb>c?b:c;}//采用分治策略intmaxSubArray(intnums[],intleft,intright){intmaxLeftSum,maxRightSum;//左右边的最人和intmaxLeftBorderSum,maxRightBorderSum;//含中间边界的左右部分最大和intleftBorderSum,rightBorderSum;//含中间边界的左右部分当前和//递归到最后的基本悄况if(left==

5、right)if(nums[left]>0)returnnu:elsereturn0;〃递归求左右部分最人值intmid=(left+right)/2,i;maxLeftSum二maxSubArray(nums,left,mid);maxRightSum二mcixSubArray(nums,mid+1,right):〃求含中间边界的左部分的最大值maxLeftBorderSum=0,leftBorderSum=0;for(i=mid;i>=left;i—){leftBorderSum+二nums[i];if(leftBorderSum>

6、mtixLeftBorderSum)maxLeftBorderSum=leftBorderSum;}〃求含中间边界的右部分的最大值maxRightBorderSum二0,rightBorderSum二0;for(i=mid+1;i<=right;i++){rightBorderSum+二nums[i];if(rightBorderSum>maxRightBordcrSum)maxRightBorderSum=rightBorderSum;//返回三者中的最大值returnmax3(maxLeftSum,maxRightSum,maxLe

7、ftBorderSum+maxRightBorderSum):}intmcixSubArrayAns(intnums[]){returnmaxSubArray(nums,0,MAX_N一1);}3、运行结果产生20个平均分布在0左右的随机故8418-1-10916-10-7-4■14-1?-418-7131325最大子段和为44.Pressanykeytocontinue4、结果分析在这个程序中采用生成随机数的方法，产生20个分布在0左右的数字。用过采用递归调用的方法，计算出最大字段和为44OS及编译环境Win764位操作系统，VC6.

8、0的编译环境