编程实现最大子段和问题的求解（分别采用分治法和动态规划法求解）

最好能用C++实现解最大子段和问题

我用的是C语言,没改成C++的,你可以自己改下:

首先用分治法:
#include "stdio.h"
int MaxSum(int a[],int left,int right)
{
int i,sum=0;
if(left==right)
sum=a[left]>0?a[left]:0;
else
{
int center=(left+right)/2;
int leftsum=MaxSum(a,left,center);
int rightsum=MaxSum(a,center+1,right);
int s1=0,s2=0,lefts=0,rights=0;

for(i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}

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;
}

void main()
{
int i,s=0;
int a[6];

printf("请输入6个整数:");
for(i=0;i<6;i++)
scanf("%d",&a[i]);

s=MaxSum(a,1,6);
printf("最大子段和为:%d",s);
}

然后是动态规划方法:
#include "stdio.h"
int MaxSum(int n,int a[])
{
int i,sum=0,b=0;
for(i=1;i<=n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
return sum;
}

void main()
{
int i,s=0;
int a[6];

printf("请输入6个整数:");
for(i=0;i<6;i++)
scanf("%d",&a[i]);

s=MaxSum(6,a);
printf("最大子段和为:%d",s);
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息