# C++ O(nlogn) solution

• ``````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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.