当前位置:文档之家› 最大字段和问题

最大字段和问题

#include
int Maxsum(int a[],int left, int right)
{
int sum=0,midsum=0,leftsum=0,rightsum=0;
int center,s1,s2,lefts,rights;
if(left==right)
sum=a[left];
else
{
center=(left+right)/2;
leftsum=Maxsum(a,left,center);
rightsum=Maxsum(a,center+1,right);
s1=0;
lefts=0;
for(int i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
s2=0;
rights=0;
for(int j=center+1;j<=right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
midsum=s1+s2;
if(midsumsum=leftsum;
else
sum=midsum;
if(sumsum=rightsum;
}
return sum;
}

void main()
{
int n,a[100],m,maxsum;
printf("请输入整数序列的元素个数\n");
scanf("%d",&n);
printf("请输入各元素的值:\n");
for(m=1;m<=n;m++)
scanf("%d",&a[m]);
maxsum=Maxsum(a,1,n);
printf("整数序列的最大子段和是:\n");
printf("%d\n",maxsum);
}

相关主题
文本预览
相关文档 最新文档