最长递增子序列（LIS），双号 [英] Longest Increasing Subsequence (LIS) with two numbers

问题描述

如何找到LIS使用两个数字的长度。 例如，     [（1,2）（7,8）（3,4）（5,6）] 另外，在上述阵列序列，LIS的长度将是3，即     [（1,2）（3,4）（5,6）] 你知道吗？

How to find the length of LIS using two numbers. For example, [(1,2) (7,8) (3,4) (5,6)] In the above array sequence, the length of LIS would be 3. i.e, [(1,2) (3,4) (5,6)] Any idea?

推荐答案

您可以使用任何<一href="http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms">algorithm对于标准的 LIS问题中，有两个修改：

You could use any algorithm for the standard LIS problem, with two modifications:

1. 忽略任何对其中第二个数字是不严格大于所述第一数量。
2. 的比较运营商对A和B（即 A＆LT; b ）需要A的第二个数字比较B的第一号
。

1. Discard any pairs where the second number isn't strictly greater than the first number.
2. The comparison operator for pairs A and B (i.e. A < B) needs to compare the second number of A to the first number of B.

这篇关于最长递增子序列（LIS），双号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！