# C++ O(nlogn) with explanation and references

• Explanation

`tails[i]` stores the Longest Increasing Subsequence of length `i+1`, of which the last element is `tails[i]`. If `tails[i]` can be of multiple values, the minimum will be taken.

So that we have `tails[0] <= tails[1] <= tails[2] <= ... <= tails[N - 1]`.

Scan the array from beginning to the end. When an new element is met, either of following cases will happen: (And this is how we construct the `tails` array)

1. The new element is larger than the tail of the longest LIS, i.e., `n > tails.back()`, then we have found a longer LIS which tail is `n`;

2. The new element is no larger than the tail of the longest LIS, but it's smaller than the tail of a "not-so-long" subsequence, then we update the tail of the "not-so-long" subsequence to the smaller one. Because the tail has become smaller, this will allow us to extend the subsequence longer later if we find a value `n <= current_tail && n > new_tail`.

So the entire problem becomes searching for a value in a sorted array. The best way? Binary search.

Code

``````#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
int lengthOfLIS(const vector<int>& nums) {
if (nums.empty())
return 0;
vector<int> tails;
tails.reserve(nums.size());
tails.push_back(nums.front());

for (size_t i = 1; i < nums.size(); ++i) {
const int& n = nums[i];
auto iter = lower_bound(tails.begin(), tails.end(), n);
if (iter == tails.end())
tails.push_back(n);
else if (n < *iter)
*iter = n;
}
return tails.size();
}
};
``````

Reference

You can find many external links on Longest increasing subsequence from Wikipedia, but the explanation is not easy to understand.

Longest Increasing Subsequence on Algorithmist gives better explanation. Take a look if you need help.

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