题解 | #最长上升子序列(一)#

class Solution {
public:
    int LIS(vector<int>& arr) {
        if(arr.size()==0)return 0;
        vector<int>dp(arr.size()+10,0x3f3f3f3f);
        int len=0;
        for(auto x:arr)
        {
            if(x>dp[len])dp[++len]=x;
            else
             {
                int l=0,r=len;
                while(l<r)
                 {
                    int mid=(l+r)>>1;
                    if(dp[mid]>=x)r=mid;
                    else l=mid+1;
                 }
                     dp[l]=x;
             }
        }
        return len+1;
    }
};