我正在重新阅读Skiena的算法设计手册，以了解自学校以来我遗忘的一些知识，而他对动态编程的描述让我有些困惑。我已经在Wikipedia和其他各种站点上进行了查找，尽管所有描述都很合理，但我自己却无法找出具体问题。目前，我正在研究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）动态编程解决方案是什么？我觉得我几乎明白了，但是我缺少一些东西。