# c++ Robinson-Schensted-Knuth Algorithm

• ``````
// 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;
}
};``````

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