Kadane算法的动态编程方面 [英] Dynamic programming aspect in Kadane's algorithm
问题描述
初始化：
max_so_far = 0
max_ending_here = 0
循环数组
（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
任何人都可以帮助我了解最佳子结构和重叠问题（面包和
根据 重叠子问题的此定义，即Kadane算法的递归公式（ f [i] = max（f [ i-1] + a [i]，a [i]））不显示此属性。每个子问题只能在朴素的递归实现中计算一次。
但是，根据其定义最优子结构。 en.wikipedia.org/wiki/Optimal_substructure rel = noreferrer>此处：我们使用较小子问题的解决方案，以便找到解决给定问题的解决方案（ f [i] 使用 f [i-1] ）。
考虑动态编程定义此处：
在数学，计算机科学，从经济上考虑，动态编程是一种通过将复杂问题分解为更简单的子问题来解决它们的方法。它适用于表现出重叠子问题 1 和最佳子结构（如下所述）的问题。如果适用，该方法所花费的时间要比不利用子问题重叠（例如深度优先搜索）的朴素方法要少得多。
动态编程的思想非常简单。通常，要解决给定的问题，我们需要解决问题的不同部分（子问题），然后组合子问题的解决方案以获得整体解决方案。通常，使用更幼稚的方法时，许多子问题会生成并解决多次。动态编程方法只尝试解决每个子问题一次，从而减少了计算量。
这为解释Kadane算法是否可以被认为是DP算法：它确实通过将问题分解为更简单的子问题来解决问题，但是其核心递归方法不会生成重叠的子问题，这是DP所要有效处理的-因此，这将使它超出DP的专业范围。 / p>
另一方面，您可以说基本递归方法没有必要导致子问题重叠，但是这将使任何递归算法成为DP算法，这将给DP一个我认为范围太广。我不知道有什么文献能完全解决这个问题，因此，我不会以学生标记书的方式标记学生或书或文章。
所以我会说它不是DP算法，只是贪婪和/或递归算法，具体取决于实现方式。由于上述原因，我将从算法的角度将其标记为贪婪，但客观上我会认为其他解释同样有效。
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
Can anyone help me in understanding the optimal substructure and overlapping problem(bread and butter of DP) i the above algo?
According to this definition of overlapping subproblems, the recursive formulation of Kadane's algorithm (f[i] = max(f[i - 1] + a[i], a[i])) does not exhibit this property. Each subproblem would only be computed once in a naive recursive implementation.
It does however exhibit optimal substructure according to its definition here: we use the solution to smaller subproblems in order to find the solution to our given problem (f[i] uses f[i - 1]).
Consider the dynamic programming definition here:
In mathematics, computer science, and economics, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems1 and optimal substructure (described below). When applicable, the method takes far less time than naive methods that don't take advantage of the subproblem overlap (like depth-first search).
The idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often when using a more naive method, many of the subproblems are generated and solved many times. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations
This leaves room for interpretation as to whether or not Kadane's algorithm can be considered a DP algorithm: it does solve the problem by breaking it down into easier subproblems, but its core recursive approach does not generate overlapping subproblems, which is what DP is meant to handle efficiently - so this would put it outside DP's specialty.
On the other hand, you could say that it is not necessary for the basic recursive approach to lead to overlapping subproblems, but this would make any recursive algorithm a DP algorithm, which would give DP a much too broad scope in my opinion. I am not aware of anything in the literature that definitely settles this however, so I wouldn't mark down a student or disconsider a book or article either way they labeled it.
So I would say that it is not a DP algorithm, just a greedy and / or recursive one, depending on the implementation. I would label it as greedy from an algorithmic point of view for the reasons listed above, but objectively I would consider other interpretations just as valid.
这篇关于Kadane算法的动态编程方面的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
