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

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 https://cp-algorithms.com/sequences/longest_increasing_subsequence.html

Thank you for your explanation.