```
class Solution {
public:
//[value, maximum_length]
int bst(vector<int>&v,int&val,int&max_len){
int right = max_len-1;
int left = 0;
while(right>=left){
int mid = (right+left)/2;
if(v[mid] == val)
return mid-1;
if(v[mid]>val)
right = mid-1;
else
left = mid+1;
}
return right;
}
int lengthOfLIS(vector<int>& nums) {
if(nums.empty())
return 0;
int max_len = 1;
vector<int> record(nums.size(),-1);
record[0] = nums[0];
for(int i = 1; i < nums.size(); i++){
int ind = bst(record,nums[i],max_len);
if(ind+2 > max_len)
max_len = ind+2;
record[ind+1] = nums[i];
}
return max_len;
}
};
```

The idea is to use an array "record" to update the minimum of the maximum of all increasing subsequences of size i.

e.g. nums = [3,8,4,6,5,7]; record = [3,4,6] at iteration i = 3. Thus on iteration 4, the incoming value nums[4] = 5. Bs on record returns index = 1. We then update record[index+1] to 5.

The update can be done using bs in O(logn), and hence it's an NlogN algorithm in total