如何使用两个数字找到LIS的长度.例如,[(1,2)(7,8)(3,4)(5,6)]在上面的数组序列中,LIS的长度为3.即[(1,2)(3, 4)(5,6)]有什么想法吗？
我不确定你在问什么,但我会假设你的意思是一对(a,b)小于另一对(c,d)当且仅当a <c和b <d时.
通过采用另一个SO线程中描述的标准动态编程技术,可以在O(N ^ 2)时间内轻松解决这个问题.
标准LIS问题的经典O(N log N)解决方案可以扩展为给出LIS问题的子二次解决方案,但存在一些困难.我们不能简单地记住每个可能长度的最小值; 我们必须保持"阶梯式"结构,其中包含每个长度的所有最小对,即,最多N个这里描述的数据结构的副本,使用键入第一个成员的有序动态对集合来实现.然后我们可以在O(log N)时间内查询该结构的一个副本(以检查它是否包含少于当前对的任何对),为二进制搜索步骤提供O(log ^ 2 N)时间,并且O(N log ^ 2 N)时间全部.这是我对问题所知的最快解决方案.