C++ O(nlogn) with explanation and references


  • 17
    X

    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.


Log in to reply
 

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