最长递增子序列问题 - returns 实际子序列的 n log n 解 - explanation/clarification 需要

Question

我已经尝试实现最长递增子序列问题的 n log n 解决方案（您需要找到最长的子序列，其中每个元素都大于给定序列的前一个元素），一个将找到最长的实际子序列（不仅仅是它的长度）。我已经完成了这个视频 - https://www.youtube.com/watch?v=S9oUiVYEq7E - 但遗憾的是我不认为视频中显示的算法是正确的 - 它似乎至少适用于视频中显示的确切输入，但不不为其他人工作，例如 [1, 8, 6, 4, 9, 8, 3, 5, 2, 7, 1, 9, 5, 7]。

from bisect import bisect_left, bisect_right
from math import floor, ceil


sequence = [3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10]
indexes = [0]
helper = [-1] * len(sequence)
for i in range(1, len(sequence)):
    if len(indexes) == 0 or sequence[i] > sequence[indexes[-1]]:
        indexes.append(i)
        helper[i] = indexes[-2]
    else:
        ceiltable = bisect_right([sequence[x] for x in indexes], sequence[i])
        indexes[ceiltable] = i
        if ceiltable > 0:
            helper[i] = indexes[ceiltable - 1]



solution = [sequence[x] for x in indexes]


print(f"longest increasing subsequence is {solution}, and has a lenght of  {len(solution)}")

我的问题是 - 任何人都可以 confirm/disconfirm 该视频中显示的算法是否真的正确，我的实现可能有什么问题？另外，我可以请任何人提供这个问题的 n log n 的简单 explanation/pseudocode/mockup 解决方案吗？我当然尝试过搜索，但我认为没有任何东西可以真正解释这个解决方案是如何工作的，或者特别是它的实现将如何工作 - 再一次，请注意，我还必须 return实际的子序列，而不仅仅是长度。

Answer 1

您引用的视频正确解释了算法。

您的实施存在两个问题：

您应该使用 bisect_left 而不是 bisect_right，否则您将允许解决方案实际上是非递减序列（具有潜在的重复值）而不是严格递增序列。而bisect_right也可能导致索引等于列表的长度，导致无效索引访问错误。（旁注：如果你真的想使用 bisect_right 并找到非递减序列，则使前面的 if 条件 >=）

代码没有将收集到的数据正确地转化为解决方案。您确实需要使用 helper 列表来追溯解决方案。这是您可以使用的代码：

solution = []
i = indexes[-1]  # start with the index of the last value of the longest sequence
while i >= 0:
    solution.append(sequence[i])
    i = helper[i]  # Look up what the optimal predecessor is of that index
solution.reverse()  # Reverse the solution since we populated it in reverse order

其他备注

您执行二进制搜索的方式效率不高，因为您使用列表推导式迭代了整个列表。这破坏了二进制搜索提供的效率。您应该为二进制搜索准备好 values，因此将它们保存在您在整个算法中维护的单独列表中，并且在二分查找。

最长递增子序列问题 - returns 实际子序列的 n log n 解 - explanation/clarification 需要

longest increasing subsequence problem - n log n solution that returns the actual subsequence - explanation/clarification needed

python

theory

algorithm

binary-search

lis

其他备注