《算法：动态规划解决最大子段和问题》由会员分享，可在线阅读，更多相关《算法：动态规划解决最大子段和问题（2页珍藏版）》请在金锄头文库上搜索。
1、算法：动态规划解决最大子段和问题/* 动态规划法思想:将较大的问题分解成较小的问题，先求解子问题，然后通过子问题的解得到原问题的解，经过分解的子问题之间并不是相互独立的。*/# 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=
2、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);
