题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003
题目描述：寻找一个序列中和值最大的子段序列，例如6，-1，5，4，-7，其最大子段和为 14（6+-1+5+4）
解题思路：运用动态规划的方法，其状态转移方程为sum=sum
并将每次的sum结果与之前的max值进行比较。
#includeint dp[100000];int main(){ int j, t, n, i, sum, max, st, ed, y, x; scanf("%d", &t); for(j=1; j 0) //sum值为正值，累加，记录当前结束点ed { sum+=dp[i]; ed=i; } if(sum max) //刷新max、st、ed { max=sum; x=st; y=ed; } } printf("Case %d:n%d %d %dn", j, max, x+1, y+1); if(j!=t) printf("n"); } return 0;}
1231和1003基本相同
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1231
#includeint dp[100000];int main(){int n,i,sum,max,st,ed,y,x;while(~scanf("%d", &n),n){ for(i=0; i 0) //sum值为正值，累加，记录当前结束点ed {sum+=dp[i]; ed=i;}if(sum max) //刷新max、st、ed {max=sum;x=st;y=ed;}}if(max>=0)printf("%d %d %dn", max, dp[x], dp[y]);elseprintf("%d %d %dn", 0, dp[0], dp[n-1]);}return 0;}
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/3589/viewspace-2804914/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
python之模块初识
下一篇：
mgo的一些用法
请登录后发表评论
登录
全部评论
