求最大子段和问题

《求最大子段和问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析实验报告学院：信息工程与自动化学院专业：软件工程141姓名：赵凛威学号：201410413111昆明理工大学信息工程与自动化学院学生实验报告（2015—2016学年第1学期）课程名称：算法设计与分析开课实验室：信口楼4452016年5月27日和6月3日年级、专业、班软工141学号201410413111姓名赵凛威成绩实验项口名称最大了段和问题指导教师吴霖教该同学是否了解实验原理：A.了解口B.慕木了解口C.不了解口

2、

3、帀该同学的实验能力：A.强口B.中等□C.差□该同学的实验是否达到要求：A.达到口B.基本达到口C.未达

4、到口451Z实验报告是否规范：A.规范口B.慕本规范口C.不规范口U实验过程是否详细记录：A.详细口B.一般□C.没有口语教师签名:年月日一、上机目的及内容1.上机内容给定有n个整数（可能有负整数）组成的序列（心,°2,・・・,禺），求改序列形如£%的子段和的k=l最大值，当所冇整数均为负整数时，其绘大子段和为0。2.上机冃的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二

5、、实验原理及基本技术路线图（方框原理图或程序流程图）三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）利用蛮力法求解:intmaxSum(inta[],intn)intmaxSum=0;intsum=0;for(inti=0;isum){sum=a[i];〃每一趟的最大值}}if(sum>m

6、axSum){maxSum=sum;}}returnmaxSum;利用分治法求解:intmaxSum(inta[],intleft,intright)intsum=0;if(left==right)〃如果序列长度为1,直接求解{if(a[leflj>0)sum=a[leftj;elsesum=0;}else{intcenter=(left+right)/2;〃划分intleftsum二maxSum(a,left,center);〃对应情况1,递归求解intrightsuni=maxSum(a,center+1,right);//对应情

7、况2,递归求解intsi=0;intlefts=0;for(inti=center;i>=left;i—)〃求解si{lefts+=a[i];if(lefts>si)si=lefts;〃左边最大值放在si}ints2=0;intrights=0;for(intj二center+1;j<=right;j++)〃求解s2rights+=a[j];if(rights>s2)s2=rights;}sum=si+s2;〃计算第3钟情况的最大子段和if(sum

8、um中取最人值if(sum0)b[i]=b[i-l]+a[i];elsefor(intj=0;jsum)sum=b

9、jj;}delete[]b;〃释放内存returnsum;}完整程序测试

10、：#include#include#includeusingnamespacestd;#defineMAX10000intBF_Sum(inta[],intn){intmax二0;intsum=0;inti,j;for(i=0;i=max){max=sum;}sum+=a[j];}}returnmax;}intmaxSuml(inta[],intleft,intright){intsum=0;

11、if(left==right)〃如杲序列长度为1,直接求解{if(a[left]>0)sum=a[left];elsesum=0;}else{intcenter二(left+right)/2;〃划分intleftsum=