```
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty())return 0;
vector<int> tail;
tail.push_back(nums[0]);
for(int x: nums){
if(x<tail[0]) tail[0]=x;
else if(x>tail.back())tail.push_back(x);
else{
int left = 0, right = tail.size();
while(left<right){
int mid = left + (right-left)/2;
if(tail[mid]>=x) right = mid;
else left = mid+1;
}
tail[left]=x;
}
}
return tail.size();
}
};
```