Patience Sort

It is an online sorting algorithm aimed to create piles of cards in such a way that piles are in increasing order down wards.

It can be used to find LIS in O(NlogN) time. Can also be used to find (minimum)number of distinct LIS.


                    VII dp;
                    for(int i=arr.size()-1;i>=0;--i)
                    {
                        int x=arr[i];
                        auto it=upper_bound(all(dp),x);
                        if(it==dp.end())
                        dp.pb(x);
                        else *it=x;
                    }
                    cout<<dp.size();

Click here for more!