```
// L is used to store the indice of elements of nums in the different-length sequences. We only store the final index in the sequence. For example, L[1] store the final index in the 1-length sequence.
// Algorithm:
// We check each element iteratively.
// For each iteration,
// if nums[i] > the last elements in the longest sequence:
// We push back i to L, which means we find a new longest sequence. Then we set R[i] = L[i - 1],
// which specifies where the previous element comes from.
// Otherwise:
// We using binary search to find L[k] where L[k] was the index of the element of nums such that nums[L[k]]
// is the ceiling of nums[i], then we replace it with i. Doing so we increases the probability of finding
// the next element for this sequence.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (!nums.size()) return 0;
vector<int> R(nums.size(), -1);
vector<int> L;
int len = 1;
L.push_back(0);
for (int i = 1; i < nums.size(); ++i) {
int n = nums[i];
if (n > nums[L.back()]) {
R[i] = L.back();
L.push_back(i);
len++;
}
else {
// Do binary search to find the element of nums contained in L which is the ceiling of n, and replace the location with i
int l = 0, r = L.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[L[mid]] == n) {
l = r = mid;
} else if(nums[L[mid]] > n) {
r = mid;
} else {
l = mid + 1;
}
}
L[l] = i;
R[i] = l == 0 ? -1 : L[l-1];
}
}
int loc = L.back();
// reversed longest sequence
// do {
// cout << nums[loc] << " ";
// loc = R[loc];
// } while (loc != -1);*/
return len;
}
};
```