1

I am trying to find ALL longest increasing subsequence of an array. I could manage to find one such LIS in O(n log n) using binary search as suggested on Wikipedia.

Can someone help me as how can I extend the same for finding ALL such LIS. I can't find better way of doing it in more than O(n²). Any suggestion to optimization would be really helpful.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Naman
  • 2,569
  • 4
  • 27
  • 44

2 Answers2

6

Consider this list:

2,1, 4,3, 6,5, 8,7, 10,9, ..., 2m,2m-1

The longest increasing sequence length of this list is m = n/2. You can trivially construct such a sequence by picking one element from each "pair" of items. Since there are m such pairs, and the choices are independent, there are 2^m longest increasing sequences.

So your algorithm can't be faster than Ω(2^(n/2)), because there's at least that much output in some cases.

To get around this you need to tweak the problem, perhaps by doing an output-sensitive analysis or by counting the number of sequences instead of actually generating them. Another alternative is to output a compact way that can be used later to generate all the sequences, which is what linear time unification algorithms do.

Craig Gidney
  • 17,763
  • 5
  • 68
  • 136
  • Hi, Thanks for such clear explanation. Can you please resolve one more doubt that whether is it possible in polynomial time just to find all the elements of all such LIS. I don't care about all sequences just the elements belonging to it. Is there any trick to do it more efficiently. – Naman May 20 '14 at 08:29
  • @Naman That can be done in `O(n lg n)` time by using dynamic programming to compute the longest length, keeping track of "items that can be before this one in the best increasing subsequence ending on this one", then following backwards-edges from the top scoring endings to see what can be reached. – Craig Gidney May 20 '14 at 12:49
  • Sorry, but I am still unable to follow. I was using same approach but I am not able to think as how that can be done in less than exponential time? Would it be possible for you to maybe expand a little bit over the finding backward-edges part? It would be really helpful. – Naman May 20 '14 at 13:45
  • @Naman That question is different enough that I [posed it separately](http://stackoverflow.com/questions/23762077/determine-which-items-in-an-array-are-part-of-longest-increasing-subsequences/23762078#23762078). – Craig Gidney May 20 '14 at 14:07
  • That is awesome. Can't thank you enough for this. I'll definitely try to implement that. – Naman May 20 '14 at 14:14
1

There can be exponentially many such sequences. You certainly cannot enumerate them in quadratic time.

You can find, in O(n log(n)) time, the length of the longest increasing subsequences starting and ending at each position in the array. Then you can enumerate all of the longest increasing subsequences by a straightforward recursion.

tmyklebu
  • 13,915
  • 3
  • 28
  • 57
  • I was using the same technique as suggested. But was wondering if it is possible to somehow optimize it maybe by having some extra structure? Or is it some kind of problem which can not be solved at all in polynomial time complexity? – Naman May 19 '14 at 17:32
  • You can't solve it in polynomial time because the output can have exponential size. Was I unclear? – tmyklebu May 19 '14 at 17:40