Is there any algorithm for "Longest increasing subsequence" with complexity less than O(n^2)?

I just want to know that while using dp for Longest increasing subsequence we get a complexity of O(n^2). Is there any other algorithm by which we can reduce the complexity???
Please explain the algo if it exists.

1 Like

There is an O(nlogn) algorithm for longest increasing subsequece, see the link
lis

You can refer this post on geeksforgeeks. It provides an nlogn solution for LIS.
This question on stackoverflow also explains the nlogn approach very well.
Take a look at this link also.

2 Likes

Yes, there is an O(nlogn) solution for LCIS. If you want to know the length, it just takes O(n) space.
But if you need to print the sequence, it MIGHT take O(n^2) space :slight_smile:

Yes, there is an O(nlogn) solution for LCIS. If you want to know the length, it just takes O(n) space. But if you need to print the sequence, it MIGHT take O(n^2) space :slight_smile:

Yes, there is an O(nlogn) solution . You can use segment tree or fenwick tree. For more details you can read this blog https://www.quora.com/What-is-the-approach-to-find-the-length-of-the-strictly-increasing-longest-subsequence.