最大子段和（分而治之求解）最大子段和（分而治之求解）
#include
#include
using namespace std;
const int Min=-99999;
void MaxSum(const vector&v,int &besti,int &bestj,int& sum,int low,int high)
{
int i;
if(low==high) //当low==high,递归截止,sum存放一个元素和
{
sum=v[low];
return;
}
else if(low=low;i--)...
最大子段和（分而治之求解）
#include
#include
using namespace std;
const int Min=-99999;
void MaxSum(const vector&v,int &besti,int &bestj,int& sum,int low,int high)
{
int i;
if(low==high) //当low==high,递归截止,sum存放一个元素和
{
sum=v[low];
return;
}
else if(low=low;i--) //求i...mid区间最大子段和
{
s+=v[i];
if(s>lbestsum)
{
L_index=i;
lbestsum=s;
}
}
int rbestsum=Min; //rbestsum是mid+1...high区间最大子段和
s=0;
int R_index; //mid_1...R_index区间是最大子段和区间
for(i=mid+1;i<=high;i++)
{
s+=v[i];
if(s>rbestsum)
{
R_index=i;
rbestsum=s;
}
}
if(lsum>rsum && lsum>(lbestsum+rbestsum)) //最大子段和是出现在low...mid区间内
{
besti=low;
bestj=mid;
sum=lsum;
}
else if(rsum>lsum && rsum>(lbestsum+rbestsum)) //最大子段和是出现在
mid+1...high区间内
{
besti=mid+1;
bestj=high;
sum=rsum;
}
else
{
besti=L_index;
bestj=R_index;
sum=lbestsum+rbestsum;
}
}
}
void main()
{
vectorv;
int i,j,sum;
sum=0;
int e;
const int end=-9999;
cin>>e;
while(e!=end)
{
v.push_back(e);
cin>>e;
}
for(i=0;i
本文档为【最大子段和（分而治之求解）】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483