求最大子段和c.c++程序实现及其效率分析

《求最大子段和c.c++程序实现及其效率分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求最大子段和1)简单蛮力算法的程序实现及其效率分析，2)分治法求解的程序实现及其效率分析，包括效率分析过程的递归求解。3)动态规划法求解的程序实现及其效率分析。分析：给定n个整数（可能为负数）组成的序列a1,a2,…,an,求该序列如的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为,例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20。解答：1）简单蛮力算法的程序实现及其效率分析程序实现：#include#includ

2、e#defineN7inta[N]={-2,11,-4,13,-5,-2,8};//用蛮力法求最大子段和intManLiFa(int*a,intn){intbesti=-1;intbestj=-1;intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){　　sum=thissum;besti=i;bestj=j;}　}}printf("起点="+besti);printf(

3、"终点="+bestj);returnsum;}intmain(){printf("蛮力法最大子段和:%d",ManLiFa(a,N));return0;　　　}效率分析：从这个算法的两个for循环可看出它的时间复杂度，T(n)=O(n2)。2）分治法求解的程序实现及其效率分析。思路：针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n2)计算时间算法进行更进一步的改进。从问题的解结构也可以看出，它适合于用分治法求解。如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2

4、+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情况：（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同（2）a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同（3）a[1:n]的最大子段和为a+…+a[j]，并且1<=i<=n/2，n/2+1<=j<=n。对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出a[n/2]，a[n/2+1]在最大子段中。因此，我们可以在a[1:n/2]中计算出s1=max(a[n/2]+a[n/2-1]+…+a),0<=i<=

5、n/2，并在a[n/2+1:n]中计算出s2=max(a[n/2+1]+a[n/2+2]+…+a)，n/2+1<=i<=n。则s1+s2为出现情况（3）的最大子段和。程序实现：#include#include#include#defineN7intMaxSubSum(int*a,intleft,intright);//分治法求最大子段和inta[N]={-2,11,-4,13,-5,-2,8};intMaxSum(int*a,intn)//a是数组,n是数组大小{

6、　　returnMaxSubSum(a,0,n-1);}//分治法intMaxSubSum(inta[],intleft,intright){inti,sum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0,lefts=0;for(i=center;i>=left

7、;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}ints2=0;intrights=0;for(i=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;if(sum

8、分析：该算法所需的计算时间T(n)可满足典型的分治算法递归分式T(n)=O(1)(nc);T(n)=2T()+O(n)n>c,由此递归方程可知，T(n)=O(nlogn)。3)动态规划算法来处理这个问题。思路：在对于上述分治算法的分析中我们注意到，若记则所求的最大子段和为由b[j]的定义可易知，当b[j-1]>0时b