算法：动态规划解决最大子段和问题算法:动态规划解决最大子段和问题
/* 动态规划法思想:将较大的问题分解成较小的问题,先求解子问题,然后通过子问题的解得到原问题的解,经过分解的子问题之间并不是
相互独立的。*/
# include
# include
# include
int max_sum(int a[],int n,int *best_i,int *best_j)
{
// *best_i表示最大子段和的起始下标
// *best_j表示最大子段和的终点下标
// i,j 表示当前子段的起点和终点下标
int ...
算法:动态规划解决最大子段和问题
/* 动态规划法思想:将较大的问题分解成较小的问题,先求解子问题,然后通过子问题的解得到原问题的解,经过分解的子问题之间并不是
相互独立的。*/
# include
# include
# include
int max_sum(int a[],int n,int *best_i,int *best_j)
{
// *best_i表示最大子段和的起始下标
// *best_j表示最大子段和的终点下标
// i,j 表示当前子段的起点和终点下标
int i,j;
int this_sum[100];
int sum[100];
int max=0;
this_sum[0]=0;
sum[0]=0;
*best_i=0;
*best_j=0;
i=1;
for(j=1;j<=n;j++)
{
if(this_sum[j-1]>=0) //判断是否为负数
this_sum[j]=this_sum[j-1]+a[j];
else
{
this_sum[j]=a[j];
i=j;
}
//如果子段和数组前一个大于下一个元素
if(this_sum[j]<=sum[j-1])
sum[j]=sum[j-1]; //对当前子段和赋值
else
{
sum[j]=this_sum[j];
*best_i=i;
*best_j=j;
max=sum[j];
}
}
return max;
}
void main()
{
int i,j,n,a[100],t;
printf("请输入数列的个数(<99):\n");
scanf("%d",&n);
printf("请输入数列元素:\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
i=j=1;
t=max_sum(a,n,&i,&j);
printf("最大字段和是:%d\n",t);
printf("字段起点是:%d\n",i);
printf("字段结束点:%d\n",j);
}
本文档为【算法：动态规划解决最大子段和问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483