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?
Asked
Active
Viewed 4,793 times
7
-
What does less-than look like? Is (1, 5) < (2, 6)? If so, the marked-answer below won't work. – Derek Illchuk Jan 24 '15 at 15:04
7 Answers
11
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.
-
-
One idea is to find lis using first coordinate only then use this sequence as input and find lis using second coordinate but not sure it will work. – mrk Aug 14 '14 at 17:35
8
You could use any algorithm for the standard LIS problem, with two modifications:
- Discard any pairs where the second number isn't strictly greater than the first number.
- 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.
NPE
- 486,780
- 108
- 951
- 1,012
-
2
-
1Bad solution, don't know why it was upvoted. Brian below gave a good one. – Szymon Feb 07 '15 at 22:13
0
Proceed as we do in case finding LIS of simple array. Just beside doing only one comparison, do compare both element. It will give LIS with O(n^2) time complexity.
Amit Pandey
- 25
- 1
- 6
0
I think you can use the standard LIS algorithm with the small exception that -
when you compare index i with index i+1 - compare the upper value of i with the lower value of i+1.
EDIT: This is of course assuming that all the ranges have the lower number first and the upper number next.
Hari
- 5,057
- 9
- 41
- 51
0
Model the problem as a graph. Each tuple can be a node. A directed edge exists from one node to another if the first tuple is strictly less than the second one (here "less" means both values of the tuple are less).
The longest increasing subsequence is now the longest path in this graph. Notice that there can be no cycles in this graph (i.e. it is a DAG). The longest path in a DAG can be found by dynamic programming (see wikipedia).
MAK
- 26,140
- 11
- 55
- 86
-
-
@saadtaame: You don't need to explicitly build a separate graph. The graph structure is already present in the problem. – MAK Sep 12 '14 at 23:26
-1
Provided the first and second number in the tuples themselves are always ascending (which seems to be the case from your example) this in principle should not be different from regular LIS algorithm besides some minor modifications: Just increase the maximum LIS up to the current tuple for which the last number is less than the first number of the current tuple. Use dynamic programming to cache maximum LIS and predecessor tuple for each sequence spot.
BrokenGlass
- 158,293
- 28
- 286
- 335
