新微赢技术网

标题: 最大子段问题分治实现错误 [打印本页]

作者: 爲眀天活着 时间: 2009-11-3 02:13
标题: 最大子段问题分治实现错误
#include<iostream.h>
int MaxSubSum(int a[],int left,int right);
int MaxSum(int n,int a[]);
int main()
{
int a[]={-2,11,-4,13,-5,-2};
int s=MaxSum(6,a);
cout<<s<<endl;
return 0;
}
int MaxSubSum(int a[],int left,int right)
{
int sum=0;
if(left==right)sum=a[align=left]>0?a[align=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(i=center+1;i<=rights;i++)
{
rights+=a[i];
if(rights>s2)s2=rights;
}
sum=s1+s2;
if(sum<leftsum)sum=leftsum;
if(sum<rightsum)sum=rightsum;
}
return sum;
}
int MaxSum(int n,int a[])
{
return MaxSubSum(a,1,n);
}
按书上算法写了下，没出现错误，输出不对，应该是20
最近经常实现一些算法，又翻出了数据结构书，感觉数据结构的实现对我来说还是有难度，真在努力中，希望高手给点建议
对大家的无私帮助表示衷心的感谢

欢迎光临新微赢技术网 (http://bbs.weiying.cn/)