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)

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 isn
; 
The new element is no larger than the tail of the longest LIS, but it's smaller than the tail of a "notsolong" subsequence, then we update the tail of the "notsolong" 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.