dynamic-programming - 最长递增子序列背后的算法

Question

我需要一个演练示例来理解以下算法。它取自 Dasgupta 的算法。这是他们给出的寻找最长递增子序列的算法。

 for j = 1, 2, . . . , n:
     L(j) = 1 + max{L(i) : (i, j) ∈ E}
 return maxj L(j)

这是图表：

我了解 L(j) 代表以 j 结尾的 LIS；但是，我不明白以下内容：max{L(i) : (i, j) ∈ E}

非常感谢一个演练示例来理解这个循环是如何工作的。谢谢！

标签： dynamic-programming

Answer 1

E 最有可能在此伪代码之前定义，它是一组对i, j，使得i < j和X_i < X_j

它只是表示所有剩余数字的 LIS 长度并且小于当前数字。Python代码：

X = [5, 2, 8, 6, 3, 6, 9, 7]
L = []
for current_value in X:
    # the whole algorithm is in this line:
    # take the LIS of a smaller preceding number and increase by one
    L.append(1 + max((l for l, x in zip(L, X) if x<current_value), default=0))
result = L[-1]