# A C++ O(nlogn) solution with the link to a nice explanation

• ``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
//Here is the explanation of the idea https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
// Binary search for the stack where the nums[i] should be pushed, according the tops of the stacks
// nums[i] cannot be push to any stack whose top is less than nums[i].
// The number of stacks is the Length of LIS.

int n = nums.size();
if( n==0 ){
return 0;
}
int end = 0;
vector<int> tops(n, INT_MIN);
tops[0] = nums[0];

for(int i=1; i<n; i++){
int idx = getIndex( tops, end, nums[i] );
tops[idx] = nums[i];
end = max( idx, end );
}

return end+1;
}
};

int getIndex( vector<int>& tops, int end, int x ){
int l = 0;
int r = end;

while( l<=r ){
int mid = (l+r)/2;
if( tops[mid] == x ){
return mid;
}
else if( tops[mid] > x ){
r = mid - 1;
}
else{
l = mid + 1;
}
}
return l;
}``````

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