23 
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

谁能帮助我理解上述算法中的最佳子结构和重叠问题（DP的面包和黄油）？

4

2 回答 2

24

根据重叠子问题的定义，Kadane 算法 ( ) 的递归公式不具有此性质。在幼稚的递归实现中，每个子问题只会计算一次。f[i] = max(f[i - 1] + a[i], a[i])

然而，根据这里的定义，它确实表现出最佳子结构：我们使用较小子问题的解决方案来找到给定问题的解决方案（使用）。f[i]f[i - 1]

考虑这里的动态规划定义：

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

动态规划背后的想法非常简单。一般来说，要解决一个给定的问题，我们需要解决问题的不同部分（子问题），然后将子问题的解决方案结合起来，达到一个整体的解决方案。通常，当使用更幼稚的方法时，会多次生成和解决许多子问题。动态规划方法试图只解决每个子问题一次，从而减少计算次数

这为 Kadane 的算法是否可以被视为 DP 算法留下了解释空间：它确实通过将问题分解为更容易的子问题来解决问题，但其核心递归方法不会产生重叠的子问题，这正是 DP 的意思有效地处理 - 所以这将使它超出 DP 的专长。

另一方面，您可以说基本递归方法没有必要导致重叠子问题，但这会使任何递归算法成为 DP 算法，这将使 DP 的范围在我看来过于宽泛。然而，我不知道文献中有任何东西可以肯定地解决这个问题，所以我不会标记学生或不考虑他们标记的书或文章。

所以我会说它不是 DP 算法，只是一个贪婪和/或递归的算法，具体取决于实现。出于上述原因，我会从算法的角度将其标记为贪婪，但客观上我会认为其他解释同样有效。

于 2013-05-01T18:43:03.983 回答
2

请注意，我从这个答案中得出了我的解释。它演示了如何将 Kadane 的算法视为具有重叠子问题的 DP 算法。

识别子问题和递归关系

想象一下，我们有一个数组a，我们想从中获取最大子数组。为了确定以索引结束的最大子数组，i以下递归关系成立：

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

为了获得a我们需要计算max_subarray_to()每个索引i的最大子数组，a然后从中获取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)

如您所见，除了最后一个索引之外max_subarray_to()，每个索引都被评估了两次，因此表明 Kadane 的算法确实有重叠的子问题i3。

Kadane 的算法通常使用自下而上的 DP 方法来实现，以利用重叠的子问题并且只计算每个子问题一次，因此将其转换为 O(n)。

于 2020-10-23T13:39:16.453 回答