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. asked 20 Jun '14, 22:55

You can refer this post on geeksforgeeks. It provides an nlogn solution for LIS. answered 21 Jun '14, 00:12

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 :) answered 21 Jun '14, 00:13

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/Whatistheapproachtofindthelengthofthestrictlyincreasinglongestsubsequence. answered 16 Jul '15, 13:41

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 :)