LeetCode 300. 最长递增子序列

LeetCode 300. 最长递增子序列

思路：

参考

代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> q;

        for(auto x:nums){
            if(q.empty() || x > q.back()) q.push_back(x);
            else{
                if(q[0] >= x){
                    q[0] = x;
                }
                else{
                    int l=0,r=q.size() - 1;
                    while(l<r){
                        int mid=l+r+1>>1;
                        if(q[mid] < x) l=mid;
                        else r=mid-1;
                    }
                    q[r + 1] = x;
                }
            }
        }
        return q.size();
    }
};