最大子段和种求解方法.doc

《最大子段和种求解方法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、最大子段和问题的简单算法：代码：#includeusingnamespacestd;intMaxSum(inta[],intn,int&besti,int&bestj){intsum=0;inti,j,k;for(i=1;i<=n;i++)for(j=i;j<=n;j++){intthissum=0;for(k=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}intmain(){intn,a[100],

2、m,i,j,maxsum;cout<<"请输入整数序列的元素个数n:"<>n;cout<<"请输入序列中各元素的值a[i](一共"<>a[m];for(m=0;m>a[m];intb[100];for(m=0;m

3、<"bestj="<usingnamespacestd;intMaxSum(inta[],intn,int&besti,int&bestj){intsum=0;inti,j,k;for(i=1;i<=n;i++){intthissum=0;for(j=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;be

4、sti=i;bestj=j;}}}returnsum;}intmain(){intn,a[100],m,i,j,maxsum;cout<<"请输入整数序列的元素个数n:"<>n;cout<<"请输入序列中各元素的值a[i](一共"<>a[m];for(m=0;m>a[m];intb[100];for(m=0;m

5、子段和是："<usingnamespacestd;intMaxSubSum(inta[],intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{i

6、ntcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}su

7、m=s1+s2;if(sum>n;cout<<"请输入序列中各元素的值a[i](一共"<>a[m];intb[100];for(m=0;m

8、cout<<"整数序列的最大子段和是："<