CODEWITHSUNDEEP
algorithmlis
Naman
Naman

Reputation: 2669

What is the most optimized algorithm to find ALL longest increasing subsequence?

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.

Upvotes: 1

Views: 836

Answers (2)

Craig Gidney
Craig Gidney

Reputation: 18266

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.

Upvotes: 6

tmyklebu
tmyklebu

Reputation: 14205

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.

Upvotes: 1

Related Questions