Consider this link. It is claimed that this algo takes O(n log n) for finding the LIS. But doesn’t the cloning steps take O(n^2) overall? Because afaik cloning an array takes O(n) time.
Anyone…?
Yes, but what is the need for cloning. (It is just for understanding I suppose).
What we essentially do is this:
Suppose you are at a[i] you find the first element just greater than a[i] in the LIS list we have made till now and replace it with a[i]. If we can’t find such element (which means a[i] is the maximum) we append it to the end of LIS.
Finding an element just greater than a[i] in a list can be done using Binary Search ( upper_bound in c++ stl) in O( log n ) time. We do this for all n element of the array so overall complexity is O ( n * log n ) .
1 Like
Thanks for the reply.
I had thought of this, but doesn’t this find only the length of the LIS and not the LIS itself then? Because we have no guarantee that lislist[i] and all except the last element of lislist[i+1] are same always. So the only thing we know for sure us the last element of lislist[i+1]. Am i correct? If so then this algo gives us the length of the lis and not the lis itself?
Yes!
However, you can get the list by maintaining parent pointers.
Read this Longest increasing subsequence - Algorithms for Competitive Programming
1 Like
Thank you for your explanation.