Kadane算法中的动态规划方面

Question

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
   (a) max_ending_here = max_ending_here + a[i]
   (b) if(max_ending_here < 0)
         max_ending_here = 0
   (c) if(max_so_far < max_ending_here)
          max_so_far = max_ending_here
 return max_so_far

有人能帮我理解上述算法中的最优子结构和重叠问题（动态规划的基础）吗？

- Bhavish Agarwal

---

据我回忆，Kadane算法是一种贪心算法。 - nhahtdh

+1，我自己也一直在苦苦思索这个问题。我无法确定它是否算作DP：我们具有最优子结构，但没有重叠的子问题。我曾看到它被标记为DP，但严格来说，我认为它不是。 - IVlad

无法想象还有人和我一样有这个问题 ;) - Eric Z

Kadane算法是贪心算法吗？那对我来说太遥远了。贪心算法的一个标志是，在算法结束时，实际解决方案，也就是当前情况下达到最大和的子数组应该已经明确计算出来了，因为“贪心算法所做的选择依赖于之前所作的选择，但不依赖于未来的选择或者子问题的所有解”，引用自维基百科关于贪心算法的文章。 - burnabyRails

@IVlad，Kadane算法给出的最终答案确实取决于解决每个子问题的所有解，其中每个子问题都是找到以特定索引结尾的数组的最大总和。最终答案是所有子问题答案中的最大值。 - burnabyRails

Answer 1

根据此对“重叠子问题”的定义，Kadane算法的递归公式（f [i] = max（f [i-1] + a [i]，a [i]））不表现出这种特性。在朴素的递归实现中，每个子问题只会计算一次。

然而，根据此对“最优子结构”的定义，它确实展现了这种特性：我们使用较小子问题的解来找到给定问题的解（f [i]使用f [i-1]）。

考虑此中的动态规划定义：

在数学、计算机科学和经济学中，动态规划是一种通过将复杂问题分解为较简单的子问题来解决问题的方法。它适用于具有重叠子问题1和最优子结构（下面描述）属性的问题。当适用时，该方法所需的时间比不利用子问题重叠（如深度优先搜索）的朴素方法要少得多。

动态规划背后的思想非常简单。通常，在解决给定问题时，我们需要解决问题的不同部分（子问题），然后组合子问题的解以达到总体解。当使用更为朴素的方法时，许多子问题会被生成并多次解决。动态规划方法寻求仅解决每个子问题一次，从而减少计算量。

这留下了解释的空间，即Kadane算法是否可以被认为是DP算法：它确实通过将问题分解为更容易的子问题来解决问题，但其核心递归方法并不生成重叠子问题，这正是DP旨在高效处理的内容——因此这将使其超出DP的专业范围。

另一方面，你可以说基本的递归方法不一定会导致重叠子问题，但这将使任何递归算法成为DP算法，这在我看来过于广泛。然而，我不知道文献中是否有明确解决这个问题的内容，因此无论他们如何标记，我都不会打分或忽视学生、书籍或文章。

因此，我认为这不是DP算法，只是贪心和/或递归算法，具体取决于实现方式。从算法的角度来看，出于上述原因，我会将其标记为贪心，但客观地说，我认为其他解释同样有效。

- IVlad

---

有趣的是，它只涉及到两个存储元素。这使得它感觉不像是典型的DP算法。你知道还有哪些算法被认为是DP算法，但所需存储空间很少吗？ - Peter de Rivaz

@PeterdeRivaz - 斐波那契递推公式具有最优子结构和重叠子问题，还可以使用O(1)内存实现。 - IVlad

请查看谷歌搜索“Kadane算法动态规划”。 - burnabyRails

我不确定你的观点是什么。我已经引用了文献定义，你有任何已发表的科学或教学材料与我所说的相矛盾吗？其他人说不同的事情并不是真正的反驳，只要他们没有具体回应我的论点。 - IVlad

Answer 2

请注意，我从这个答案中提取了我的解释。它展示了Kadane算法可以被视为具有重叠子问题的DP算法。

确定子问题和递推关系

假设我们有一个数组 a，我们希望从中获取最大子数组。要确定以索引 i 结尾的最大子数组，以下递归关系成立：

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

为了获得数组 a 的最大子数组，我们需要计算 a 中每个索引 i 的 max_subarray_to()，然后从中取出最大值 max()。

max_subarray = max( for i=1 to n max_subarray_to(i) )

示例

现在，假设我们有一个数组[10,-12,11,9]，我们想要获得最大子数组。 运行Kadane算法将需要执行以下工作：

result = max(max_subarray_to(0), max_subarray_to(1), max_subarray_to(2), max_subarray_to(3))

max_subarray_to(0) = 10  # base case
max_subarray_to(1) = max(max_subarray_to(0) + (-12), -12)
max_subarray_to(2) = max(max_subarray_to(1) + 11, 11)
max_subarray_to(3) = max(max_subarray_to(2) + 9, 49)

正如您所看到的，除了最后一个索引3之外，每个i对应的max_subarray_to()都被评估两次，因此表明Kadane算法确实存在重叠子问题。通常使用自底向上的DP方法来实现Kadane算法，以利用重叠子问题并只计算每个子问题一次，从而将其转换为O(n)。

- arauter

---

Dijkstra算法也可以递归地编写，如果你真的想这样做的话（例如：http://thoughtoverflow.com/dsa/dijkstra-shortest-path-recursive.html - 我相信比我更有技巧的人可以在比我愿意花费的时间更短的时间内提出递归公式）。现在考虑从源节点开始找到所有最短路径中最长的路径：它将涉及取dijkstra（node_1），dijkstra（node_2）等的最大值。如果您像之前那样编写它，我们在这里也会有重叠的子问题。那么这是否是DP呢？ - IVlad

如果你这样做，你可以强制任何问题成为DP问题，但在我看来，这似乎违背了DP定义的精神，因为尽可能多地在一个函数中完成所有操作只是为了强制递归调用生成重叠子问题。例如考虑f(i) = f(i-1) + 1, g(i) = max(g(i-1), f(i))。这是DP吗？f(i)计算f(i-1)，g(i-1)也是如此。它符合定义，是的。但这很混乱，而且这是你滥用递归的错。f本身不是DP，你最好将计算f视为一个单独的问题。 - IVlad

@IVlad，Dijkstra算法的维基百科文章将Dijkstra算法归类为“动态规划”。当然，Kadane算法被广泛认为是动态规划（以及贪心算法）。 - burnabyRails

@burnabyRails，即使在维基百科上，该分类也被标记为有争议。 CLRS（维基页面上的第一个引用）将其归类为贪婪算法。 - IVlad

@IVlad，你提出了一些非常好的观点，关于强制问题成为DP以检索重叠子问题。我理解为什么这可以成为我在这里回答的论据，并且为什么你的答案因此似乎更正确。感谢您的反馈。 - Andi