algorithm - 具有两个数字的最长递增子序列 (LIS)

Question

如何使用两个数字求出 LIS 的长度。例如， [(1,2) (7,8) (3,4) (5,6)]在上面的数组序列中，LIS 的长度为 3。即， [(1,2) (3,4) (5,6)]有什么想法吗？

Answer 1

我不确定你在问什么，但我会假设你的意思是当且仅当 a < c 和 b < d 时，一对 (a,b) 小于另一对 (c,d)。

这可以通过采用标准动态规划技术在 O(N^2) 时间内轻松解决，描述为 in another SO thread .

经典 O(N log N) solution to the standard LIS problem可以扩展为成对的 LIS 问题的次二次解，但有一些困难。我们不能简单地记住每种可能长度的一个最小值；我们必须维护包含每个长度的所有最小对的“阶梯状”结构，即最多 N 个描述的数据结构副本 here ，使用以第一个成员为键的有序动态对集实现。然后我们可以在 O(log N) 时间内查询该结构的一个副本(以检查它是否包含小于当前对的任何对)，为二进制搜索步骤提供 O(log^2 N) 时间，并且 O(N总共 log^2 N) 时间。这是我所知道的最快的问题解决方案。