编程论坛 → C++教室

最大子段问题分治实现错误

diaoxue 发布于 2007-10-21 21:28， 790 次点击

#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
最近经常实现一些算法，又翻出了数据结构书，感觉数据结构的实现对我来说还是有难度，真在努力中，希望高手给点建议
对大家的无私帮助表示衷心的感谢

5 回复

#2

cwande2007-10-21 22:25

最大子段和的动态规划解法比分治法简单,又好实现多了

#3

nuciewth2007-10-22 10:29

的确DP解法好多了.

#4

jxnuwy042007-10-22 12:20

既然编译运行都正常，就是结果不对，那就是逻辑上出了问题了，应该单步调试一下。

#5

diaoxue2007-10-22 16:32

动态规划算法已经实现了,算法很简单
这算法我只是实现下,练习下
单步调试,vc我不会,又不象matlab

#6

diaoxue2007-10-22 23:00

#include <iostream.h>
#include <stdlib.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;
system("pause");
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 <= right; 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, 0, n - 1);
}
搞定

1