蛮力法、分治法和动态规划法设计最大子段和问题的算法

fts+=a[i];Р if (lefts>s1) s1=lefts;Р y++;Р }Р s2=0; rights=0; //再求解s2Р for (j=center+1; j<=right; j++)Р { Р rights+=a[j];Р if (rights>s2) s2=rights;Р y++;Р }Р sum=s1+s2; //计算情况③的最大子段和Р if (sum<leftsum) sum=leftsum; Р //合并,在sum、leftsum和rightsum中取较大者Р if (sum<rightsum) sum=rightsum;Р y++;Р }Р return sum;Р}Рint max(int a[],int n)Р{Р int sum=0,b=0;Р for(int i=0;i<=n;i++)Р {Р if(b>0)Р b+=a[i];Р else b=a[i];Р if(b>sum)Р sum=b;Р z++;Р }Р return sum;Р}Рvoid main()Р{Р?int c;Р?int s[5]={1,9,-5,7,-1};Р c=ml(s);Р cout<<"蛮力法计算最大子段和为:"<<c<<endl;Р cout<<"蛮力法时间性为:"<<x<<endl;Р?c=MaxSum(s, 0, 4);Р cout<<"分治法计算最大子段和为:"<<c<<endl;Р cout<<"分治法时间性为:"<<y<<endl;Р?c=max(s, 4);Р cout<<"动态规划法计算最大子段和为:"<<c<<endl;Р cout<<"动态规划法时间性为:"<<z<<endl;Р}Р程序运行结果:Р实验结果分析Р程序测试序列为1 ,9 , -5 , 7, -1Р最大子段和为12。Р由上述程序结果分析动态规划法较其他算法而言较优。