资源预览内容
亲,该文档总共2页全部预览完了,如果喜欢就下载吧!
资源描述
算法:动态规划解决最大子段和问题/* 动态规划法思想:将较大的问题分解成较小的问题,先求解子问题,然后通过子问题的解得到原问题的解,经过分解的子问题之间并不是相互独立的。*/# 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_sum100;int sum100;int max=0;this_sum0=0;sum0=0;*best_i=0;*best_j=0;i=1;for(j=1;j=0) /判断是否为负数this_sumj=this_sumj-1+aj;elsethis_sumj=aj;i=j;/如果子段和数组前一个大于下一个元素if(this_sumj=sumj-1)sumj=sumj-1; /对当前子段和赋值elsesumj=this_sumj;*best_i=i;*best_j=j;max=sumj;return max;void main()int i,j,n,a100,t;printf(请输入数列的个数(99):n);scanf(%d,&n);printf(请输入数列元素:n);for(i=1;i=n;i+)scanf(%d,&ai);i=j=1;t=max_sum(a,n,&i,&j);printf(最大字段和是:%dn,t);printf(字段起点是:%dn,i);printf(字段结束点:%dn,j);
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号