欢迎来到天天文库
浏览记录
ID:58414039
大小:33.00 KB
页数:5页
时间:2020-05-11
《最大子段和种求解方法.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;m3、<"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;be4、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;m5、子段和是:"<usingnamespacestd;intMaxSubSum(inta[],intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{i6、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;}su7、m=s1+s2;if(sum>n;cout<<"请输入序列中各元素的值a[i](一共"<>a[m];intb[100];for(m=0;m8、cout<<"整数序列的最大子段和是:"<
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;m5、子段和是:"<usingnamespacestd;intMaxSubSum(inta[],intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{i6、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;}su7、m=s1+s2;if(sum>n;cout<<"请输入序列中各元素的值a[i](一共"<>a[m];intb[100];for(m=0;m8、cout<<"整数序列的最大子段和是:"<
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;m8、cout<<"整数序列的最大子段和是:"<
8、cout<<"整数序列的最大子段和是:"<
此文档下载收益归作者所有