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
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 
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
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.