# Very concise O(nlogn) C++ implementation with explanation

• Suppose you've already understood the O(n^2) solution. Let LIS[i] be the minimum last integer of a length i sequence. Suppose we have the following sequence

``````1 3 2 5 4
``````

and we've handled [1, 3, 2, 5]. The corresponding LIS[] would be [INT_MIN, 1, 2, 5](indexes starting from 0). Now we wanna handle 4, i.e., the longest increasing sequence end with 4, we can do a binary search to find the largest integer less than 4. In this case, it should be LIS[2] = 2. Note that the LIS[] should always be an increasing sequence so we can do binary search. Now we got a sequence of length 3 end with 4, so we can update LIS[3] = min(LIS[3], 4). However, if the number we are handling is 7 instead of 4, we get a sequence of length 4 end with 7, which is longer than any existing sequence, then we can simply append the new value to the tail of LIS[]. We can generalize that the new LIS[] will still be increasing sequence. After handled all the integers, the size of LIS[] - 1 would be the desired result.

``````class Solution {
public:
int binsearch(vector<int>& LIS, int val) {
int l = 0, r = LIS.size();
while (l < r - 1) {
int m = (l + r) / 2;
if (LIS[m] < val)
l = m;
else
r = m;
}
return l;
}
int lengthOfLIS(vector<int>& nums) {
vector<int> LIS;
LIS.push_back(INT_MIN);
for (int i = 0; i < nums.size(); ++i) {
int l = binsearch(LIS, nums[i]);
if (l + 1 == LIS.size())
LIS.push_back(nums[i]);
else
LIS[l + 1] = min(LIS[l + 1], nums[i]);
}
return LIS.size() - 1;
}
};``````

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