|
以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- 关于一道动态规划的编程题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=85956) |
|
-- 作者：watchingsky -- 发布时间：7/30/2010 3:56:00 PM -- 关于一道动态规划的编程题 最近在看动态规划的知识，有一道题是这样的 找出一个数列的子序列，使子序列的各数字之和最大 例如 数列 5， 15， -30， 10， -5， 40， 10 的最大子序列是 10， -5， 40， 10，它们的和是55。（注，子序列中的数字在原序列中必须是连续的，即如5,15,10这样的序列不是子序列） 我列出了递推公式如果设S(k)为原序列中从1...k数字的最长子序列，a(k)为k位置上的数(k= 1 ... N)。设数列的长度为N，那么所求的结果为S(N).递推的公式为 但是在写程序时遇到了困难，不知道如何将公式转化为程序(应该如何设置数组和循环）。请大家指点，谢谢。
[此贴子已经被作者于2010-7-30 16:43:31编辑过]
|
|
-- 作者：zet809 -- 发布时间：8/20/2010 4:21:00 PM -- for (i = 0; i < queue_size; i++) { line_sum = 0; for (j = i; j < queue_size; j++) { line_sum += queue[j]; if(line_sum > max_sum) { max_sum = line_sum; //和最大值 max_sum_start = i; //最大值起始位置 max_sum_distance = j - i + 1; //字串长度 } } } |
|
-- 作者：wmkevin -- 发布时间：11/21/2010 8:52:00 PM -- 这个问题我以前看到过~ 你的思路木有问题 其实对其分情况就可以 如果累加和出现负数了就把暂时的累加和清空为零，因为负数加后续的数肯定会小于后续的数直接相加，如果是正数，就继续加下去 即套用你的公式为S(j)=max{S(j-1)+a(j),S(j-1)} 之前子数列最大和假设为max temp=s(j-1)+a(j); if(temp<0)sum=0; else{if(temp)>max; max=temp} 这样写不知道你是否可以明白呢 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
62.500ms |