c++ Robinson-Schensted-Knuth Algorithm


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

Log in to reply
 

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