动态规划法求最大字段和.doc

实验题目 给定由n个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 实验内容（包括代码和对应的执行结果截图） 实验代码如下: #includeiostream using namespace std; //蛮力法求解最大字段和问题 int mlf(int a[],int s[][6]) { int i,j,k=0; for(i=0;i6;i++) s[i][i]=a[i]; for(i=0;i6;i++) for(j=i+1;j6;j++) s[i][j]=s[i][j-1]+a[j]; for(i=0;i6;i++) for(j=i;j6;j++) if(s[i][j]k) k=s[i][j]; if(k0) k=0; return k; } //分治法求解最大字段和问题 int MaxSum(int a[],int left,int right) { int sum=0; if(left==right) { //如果序列长度为1，直接求解 if (a[left]0) sum=a[left]; else sum=0; } else { int center=(left+right)/2; //划分 int leftsum=MaxSum(a,left,center); //对应情况①，递归求解 int rightsum=MaxSum(a,center+1,right); //对应情况②，递归求解 int s1=0; int lefts=0; //以下对应情况③，先求解s1 for (int i=center;i=left;i--) { lefts+=a[i]; if (leftss1) s1=lefts; } int s2=0; int rights=0; //再求解s2 for (int j=center+1;j=right;j++) { rights+=a[j]; if (rightss2) s2=rights; } sum=s1+s2; //计算情况③的最大子段和 if (sumleftsum) sum=leftsum; if (sumrightsum) sum=rightsum; //合并，在sum、leftsum和rightsum中取较大者 } return sum; } //动态规划法求解最大字段和问题 int dtghf(int n,int a[]) { int sum=0; int b=0; for(int i=0;in;i++) { if(b0) b+=a[i]; else b=a[i]; if(bsum) sum=b; } return sum; } void main() { cout输入六个整数:endl; int a[6]; for(int i=0;i6;i++) { cina[i]; } int s[6][6]={0}; int maxsum=mlf(a,s); cout蛮力法求解最大子段和为:maxsumendl; maxsum=MaxSum(a,0,5); cout分治法求解最大子段和为:maxsumendl; maxsum=dtghf(6,a); cout动态规划法求最大子段和为:maxsumendl; } 实验结果截图如下: 实验总结: 该实验表明同一个问题可以用不同