最大子段和三种求解方法1、最大子段和问题的简单算法:
代码:
#include
using namespace std;
int MaxSum(int a[],int n,int &besti,int &bestj){
int sum=0;
int i,j,k;
for(i=1;isum){
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
int main(){
int n,a[100],m,i,j,maxsum;
cout>n;
cout>a[m]...
1、最大子段和问题的简单算法:
代码:
#include
using namespace std;
int MaxSum(int a[],int n,int &besti,int &bestj){
int sum=0;
int i,j,k;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
int thissum=0;
for(k=i;k<=j;k++)thissum+=a[k];
if(thissum>sum){
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
int main(){
int n,a[100],m,i,j,maxsum;
cout<<"请输入整数序列的元素个数n:"<>n;
cout<<"请输入序列中各元素的值a[i](一共"<>a[m];
for(m=0;m>a[m];
int b[100];
for(m=0;m
using namespace std;
int MaxSum(int a[],int n,int &besti,int &bestj){ int sum=0;
int i,j,k;
for(i=1;i<=n;i++){
int thissum=0;
for(j=i;j<=n;j++)
{
thissum+=a[j];
if(thissum>sum){
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
int main(){
int n,a[100],m,i,j,maxsum;
cout<<"请输入整数序列的元素个数n:"<>n;
cout<<"请输入序列中各元素的值a[i](一共"<>a[m];
for(m=0;m>a[m];
int b[100];
for(m=0;m
using namespace std;
int MaxSubSum(int a[],int left,int right){
int sum=0;
if(left==right)sum=a[left]>0?a[left]:0;
else{
int center=(left+right)/2;
int leftsum=MaxSubSum(a,left,center);
int rightsum=MaxSubSum(a,center+1,right);
int s1=0;
int lefts=0;
for(int i=center;i>=left;i--){
lefts+=a[i];
if(lefts>s1)s1=lefts;
}
int s2=0;
int rights=0;
for(int i=center+1;i<=right;i++){
rights+=a[i];
if(rights>s2)s2=rights;
}
sum=s1+s2;
if(sum>n;
cout<<"请输入序列中各元素的值a[i](一共"<>a[m];
int b[100];
for(m=0;m
using namespace std;
int MaxSum(int n,int a[]){
int sum=0;
int b=0;
for(int i=1;i<=n;i++){
if(b>0)b+=a[i];
else b=a[i];
if(b>sum)sum=b;
}
return sum;
}
int main(){
int n,a[100],m,maxsum;
cout<<"请输入整数序列的元素个数n:"<>n;
cout<<"请输入序列中各元素的值a[i](一共"<>a[m];
int b[100];
for(m=0;m
本文档为【最大子段和三种求解方法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483