动态规划法求最大字段和

《动态规划法求最大字段和》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验题目给定由个整数组成的序列(al,a2,…，az?)，求该序列形如k=i的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。实验目的(1)深刻掌握动态规划法的设计思想并能熟练运用；(2)理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。实验内容(包括代码和对应的执行结果截图)实验代码如下：#includeusingnamespacestd;//蛮力法求解最大字段和问题intmlf(inta[]，ints[][6])inti，j，k=O;for(i=0;i<6;i++)s剛=a[i];

2、for(i=0;i<6;i++)for(j=i+l;j<6;j++)s[i][j]=s[i]U-l]+a[j];for(i=0;i<6;i++)for(j=i;j<6;j++)if(s[i]U]〉k)k=s[i][j];if(k<0)k=0;returnk;}//分治法求解最大字段和问题intMaxSum(inta[l,intleft,intright)intsum=O;if(left==right){//如果序列长度为1，直接求解if(a[left]〉O)sum=a[left];elsesum=O;}else{intcenter=(left+right

3、)/2;"划分intleftsum=MaxSum(a,left,center);//对应情况①，递伯求解intrightsum=MaxSum(a，center+l,right);//对应情况②，递归求解intsl=O;intlefts=O;//以下对成情况③，先求解sifor(inti=center;i〉=left;i--){lefts+=a[i];if(lefts〉sl)sl=lefts;}ints2=0;intrights=0;//再求解s2for(intj=center+1;j<=right;j++)rights+=a[j];if(rights〉s

4、2)s2=rights;}sum=sl+s2;//计算情况③的最大子段和if(sumsum)sum=b;}returnsum;}voidmain(){cout«n输

5、入六个整数:"<entsandSettingsAd>inistrator桌

6、面Debugshiyan5.exeM020R-••©22-c>u•■••ST/n为为和ti和—on-2農子c5子H^Kto-大大最y数13曰署5ke整4解解法y个•裘划an六11法壞S入0力塞es输H2蛮分动pr瞭狗拼音半，实验总结:该实验表明同一个问题可以用不同的方法解决。应用蛮力法求解最大字段和问题的时间复杂度为0(n2)。应用分治法求解，对应划分得到的情况①和②，需要分别递归求解，对应情况③，两个并列for循环的时间复杂性是0(〃)，所以，存在如下递推式f1n=lr(z?)=[2r(n/2)+z7n>l根据1.2.4节主定理，算法4.7的时间

7、复杂性为O(nlog2At)。应用动态规划法求解，其思想是将问题划分为若干个子问题，但这些子问题不一定独立，用一个表格把每个子问题的解保存起来，当用到该子问题的解时查表即可，从而避免了大量的重复计算。其时间复杂度为0(n),所以从时间性能上比蛮力法好。