我如何才能找到使用动态规划的子序列的最高金额？ [英] How can I find the maximum sum of a sub-sequence using dynamic programming?

问题描述

我重新阅读Skiena的算法设计手册追赶上一些东西，因为学校里，我已经忘记了，我就是一个通过动态规划他的描述有点百思不得其解。我已经在维基百科和其他各种网站看它，虽然描述的所有意义，我无法搞清楚具体问题我自己。目前，我工作的问题3-5从Skiena书。 （给定n个实数的数组，发现在输入的任何连续子向量的最高金额。）我有一个为O（n ^ 2）的解决方案，如<一个描述href="http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming">this回答。但我卡在使用动态规划的O（N）解决方案。目前还不清楚我是什么递推关系应该是。

I'm re-reading Skiena's Algorithm Design Manual to catch up on some stuff I've forgotten since school, and I'm a little baffled by his descriptions of Dynamic Programming. I've looked it up on Wikipedia and various other sites, and while the descriptions all make sense, I'm having trouble figuring out specific problems myself. Currently, I'm working on problem 3-5 from the Skiena book. (Given an array of n real numbers, find the maximum sum in any contiguous subvector of the input.) I have an O(n^2) solution, such as described in this answer. But I'm stuck on the O(N) solution using dynamic programming. It's not clear to me what the recurrence relation should be.

我看到子序列形成集款项的，就像这样：

I see that the subsequences form a set of sums, like so:

S = {A，B，C，D}

S = {a,b,c,d}

a    a+b    a+b+c    a+b+c+d
     b      b+c      b+c+d
            c        c+d
                     d

我不明白是怎么选哪一个是最大的线性时间。我试着做这样的事情跟踪的最大一笔为止，如果当前值是正的，把它添加到总和。但是，当你有较大的序列，这成为问题，因为有可能是负数的延伸，将降低的总和，但后来大的正数可以将其带回成为最大的。

What I don't get is how to pick which one is the greatest in linear time. I've tried doing things like keeping track of the greatest sum so far, and if the current value is positive, add it to the sum. But when you have larger sequences, this becomes problematic because there may be stretches of negative numbers that would decrease the sum, but a later large positive number may bring it back to being the maximum.

我也提醒总结面积表。你可以计算所有只用累计金额的款项：A，A + B，A + B + C，A + B + C + D等（例如，如果你需要B + C，它只是（A + B + C） - （一）），但没有看到一个O（N）的方式来得到它

I'm also reminded of summed area tables. You can calculate all the sums using only the cumulative sums: a, a+b, a+b+c, a+b+c+d, etc. (For example, if you need b+c, it's just (a+b+c) - (a).) But don't see an O(N) way to get it.

任何人都可以向我解释什么了O（N）动态规划的解决方案是为这个特殊的问题？我觉得我几乎得到它，但我失去了一些东西。

Can anyone explain to me what the O(N) dynamic programming solution is for this particular problem? I feel like I almost get it, but that I'm missing something.

推荐答案

您应该的一起来看看这个PDF 回到学校 http://castle.eiu.edu 那就是：

You should take a look to this pdf back in the school in http://castle.eiu.edu here it is:

下面的伪code的解释也诠释了PDF格式。

The explanation of the following pseudocode is also int the pdf.

这篇关于我如何才能找到使用动态规划的子序列的最高金额？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！