why after applying binary search i.e. upper bound condn we are still checking if arr(i) is greater than dp(pos-1) where pos is the idx that we obtained using upper_bound()?
About the code implementation of LIS in O(nlogn) TC
Hey @Senjuti256 suppose you have to find upper_bound of number x. And there is no number bigger then x. Then there’s no need of checking if arr(i) is greater than dp(pos-1).
You can handle this x element as the last element of your dp sequence.
But for other elements why are we doing so?
It’s because if there will be any number which will be greater then that number, then we have to consider that instead of this number. Moreover i would suggest you to see this video one more time as it’s explained in detail, if you will still have any doubt, you can ask it for sure.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.