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.
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 ) .
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?
However, you can get the list by maintaining parent pointers.
Read this https://cp-algorithms.com/sequences/longest_increasing_subsequence.html
Thank you for your explanation.