如何使用动态编程找到子序列的最大总和？

Question

我正在重新阅读Skiena的算法设计手册,以了解自学校以来我忘记的一些东西,我对他对动态编程的描述感到有点困惑.我看着它在维基百科和其他各种网站,并同时说明一切意义,我无法找出具体的问题我自己.目前,我正在从Skiena的书中解决问题3-5.(给定一个n个实数的数组,找到输入的任何连续子向量中的最大总和.)我有一个O(n ^ 2)解决方案,如本答案中所述.但我坚持使用动态编程的O(N)解决方案.我不清楚复发关系应该是什么.

我看到子序列形成一组总和,如下所示:

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

我没有得到的是如何选择哪一个在线性时间内最大.到目前为止,我已经尝试过跟踪最大值的事情,如果当前值为正,则将其添加到总和中.但是当你有更大的序列时,这就成了问题,因为可能有一些负数会减少总和,但是后来的大正数可能会使它恢复到最大值.

我还想起了总面积表.你可以只使用累积和来计算所有的总和:a,a + b,a + b + c,a + b + c + d等等(例如,如果你需要b + c,它只是(a +) b + c) - (a).)但是没有看到O(N)方法来获得它.

任何人都可以向我解释一下这个特定问题的O(N)动态编程解决方案是什么吗？我觉得我几乎得到它,但我错过了一些东西.

Answer 1

您应该在学校http://castle.eiu.edu 上看一下这个pdf,这里是:

以下伪代码的解释也在pdf中.