如何使用两个数字求出 LIS 的长度。 例如， [(1,2) (7,8) (3,4) (5,6)] 在上面的数组序列中，LIS 的长度为 3。即， [(1,2) (3,4) (5,6)] 有什么想法吗？
最佳答案
我不确定你在问什么，但我会假设你的意思是当且仅当 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) 时间。这是我所知道的最快的问题解决方案。
关于algorithm - 具有两个数字的最长递增子序列 (LIS)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8716934/