algorithm - 如何使用动态规划找到子序列的最大总和？

Question

我正在重读 Skiena 的《算法设计手册》，以弥补自学校以来我忘记的一些内容，我对他对动态规划的描述感到有些困惑。我在维基百科和其他各种网站上查找过，虽然描述都很有道理，但我自己却无法找出具体问题。目前，我正在研究 Skiena 书中的问题 3-5。 (给定一个包含 n 个实数的数组，找到输入的任何连续子向量中的最大总和。)我有一个 O(n^2) 解决方案，如 this answer 中所述。 .但是我坚持使用动态编程的 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

你应该take a look to this pdf回到学校 http://castle.eiu.edu这是:

下面伪代码的解释也是在pdf中。