300

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lis;
        for(auto num : nums){
            int pos = lower_bound(lis.begin(), lis.end(), num)-lis.begin();
            if(pos == lis.size())
                lis.push_back(num);
            else
                lis[pos] = num;
        }
        return lis.size();
    }
};