logo标签列表

如何使用动态规划找到最大子序列之和？

algorithmdynamic-programming
9
我正在重新阅读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）动态编程解决方案是什么？我觉得我几乎明白了，但似乎还漏了些什么。
3个回答
11
2
我对这张图表感到困惑，因为它跳过了几个子序列（例如[5, 15]和[15, -30]）。但我会仔细阅读PDF文件，看看是否更容易理解。谢谢！ - user1118321
好的，在阅读了它之后，现在它更加有意义了。非常感谢！ - user1118321
6
@cMinor的链接失效了。 - Cacho Santa
经过多次搜索，这似乎是少数几个具有正确定义的地方之一 - 但链接已经失效。 - whizvids
如果所有数字都是负数，给定的伪代码将无法工作。 - jblixr
@jblixr 假设空序列的总和为0，这是合理的，因为0是加法的单位元。如果所有数字都是负数，则空序列是最大子序列。 - matj1
2
我的理解是DP就是“制表法”。其实，DP中的“Programming”原意就是制表。
关键是要弄清楚“在表格中放什么”，或者用现代术语来说：要跟踪什么状态，或者在DAG中跟踪顶点的键/值是什么（如果这些术语听起来很奇怪，请忽略它们）。
比如，选择dp[i]表表示数组以索引i结尾的最大和，例如，数组为[5, 15, -30, 10]。
第二个重要的关键是“最优子结构”，也就是“假设”dp[i-1]已经存储了以索引i-1结尾的子序列的最大和。因此，在i处的唯一步骤就是决定是否将a[i]包含在子序列中。
dp[i] = max(dp[i-1], dp[i-1] + a[i])
< p > max 中的第一个项是“不包括 a [i]”，第二个项是“包括 a [i]”。请注意，如果我们不包括 a [i]，到目前为止最大的和仍然是来自“最优子结构”论证的 dp [i-1]。

因此，整个程序如下所示（使用 Python）：

a = [5,15,-30,10]

dp = [0]*len(a)
dp[0] = max(0,a[0]) # include a[0] or not

for i in range(1,len(a)):
    dp[i] = max(dp[i-1], dp[i-1]+a[i]) # for sub-sequence, choose to add or not     


 print(dp, max(dp))

结果：最大子序列的和应该是在dp表中最大的项，在i遍历数组a后。但仔细看看dp，它保存了所有信息。
由于它只对数组a中的项进行一次遍历，因此它是一个O(n)算法。
这个问题似乎很傻，因为只要a[i]是正数，我们就应该始终将其包含在子序列中，因为它只会增加总和。这种直觉与代码相符。
dp[i] = max(dp[i-1], dp[i-1] + a[i])

因此，最大子序列和问题很容易解决，根本不需要使用动态规划。简单来说，
sum = 0
for v in a:
     if  v >0
         sum += v

然而，对于“连续子数组最大和”问题，我们只需要更改一行代码。

dp[i] = max(dp[i-1]+a[i], a[i])

第一个术语是“将a[i]包含在连续的子数组中”，第二个术语是决定开始一个新的子数组，从a[i]开始。
在这种情况下，dp[i]是以索引i结尾的最大和连续子数组。
这肯定比天真的方法O(n^2)*O(n)更好，对于i循环内的for j in range(0,i)和sum所有可能的子数组。
有一个小注意点，因为设置了dp[0]的方式，如果a中的所有项都为负数，我们将不会选择任何项。因此，对于最大和连续子数组，我们将其更改为：
dp[0] = a[0]
顺便提一下，max(dp) 而不是 dp[-1] 是因为子序列或子数组可能不包括数组的最后一个元素。 - Zhe Hu
1
有一个解决方案，首先将数组排序到一些辅助内存中，然后将最长公共子序列方法应用于原始数组和排序后的数组，在表格（记忆化）中使用两个数组中公共子序列的总和（而不是长度）作为条目。这也可以解决问题。
总运行时间为O(nlogn)+O(n^2) => O(n^2) 空间为O(n) + O(n^2) => O(n^2)
当内存变得重要时，这不是一个好的解决方案。这只是为了让人们了解如何将问题归约到另一个问题。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接