Longest Increasing Subsequence (LIS) with two numbers

Question

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?

Answer 1

I'm not sure what you are asking but I will assume what you mean is that a pair (a,b) is less than another pair (c,d) if and only if a < c and b < d.

This can be easily solved in O(N^2) time by adapting the standard dynamic programming technique, which is described in another SO thread.

The classic O(N log N) solution to the standard LIS problem can be extended to give a subquadratic solution to the LIS problem with pairs, with some difficulty. We cannot simply remember one minimum value for every possible length; we have to maintain "staircase-like" structures containing all minimal pairs for each length, that is, up to N copies of the data structure described here, implemented using an ordered dynamic set of pairs keyed on the first member. We can then query one copy of this structure in O(log N) time (to check whether it contains any pair less than the current pair), giving O(log^2 N) time for the binary search step, and O(N log^2 N) time in all. This is the fastest solution I know to the problem.

Answer 2

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

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.