聪明文档网
最新最全的文档下载
当前位置：
首页> 算法：动态规划解决最大子段和问题
算法：动态规划解决最大子段和问题
时间：2023-02-02 20:03:25 下载该word文档
算法：动态规划解决最大子段和问题/*动态规划法思想:将较大的问题分解成较小的问题，先求解子问题，然后通过子问题的解得到原问题的解，经过分解的子问题之间并不是相互独立的。*/#include#include#includeintmax_sum(inta[],intn,int*best_i,int*best_j{//*best_i表示最大子段和的起始下标//*best_j表示最大子段和的终点下标//i,j表示当前子段的起点和终点下标inti,j;intthis_sum[100];intsum[100];intmax=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];}
returnmax;}voidmain({inti,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;
Word文档免费下载：
算法：动态规划解决最大子段和问题
-
1个月 推荐
￥29.8
￥45每天只需1.0元 -
1天
￥9.9
￥15 -
3个月
￥59.8
￥90
选择支付方式
-
微信付款
郑重提醒：支付后，系统自动为您完成注册
