How to approach this problem in nlogn time?

#1

I had seen some videos on youtube where the same problem longest increasing subsequence was being implemented in nlogn time .Please expain how can we do so as their explaination was not so clear.

#2

@TusHar-AroRa-2294450460870717 hi bro,The trick for the nlogn solution is to maintain, in addition to your dp table, an auxiliary table A so that A[ i ] holds the information “what is the minimum number in the array, such that an increasing subsequence of length i terminates at”, it is easy to see that this array will be strictly increasing. Therefore, we can simply binary search the solution of every subproblem and update our array. Also please refer to these slides one time ,you will get all clear: