Very concise O(nlogn) C++ implementation with explanation


  • 2
    L

    Suppose you've already understood the O(n^2) solution. Let LIS[i] be the minimum last integer of a length i sequence. Suppose we have the following sequence

    1 3 2 5 4
    

    and we've handled [1, 3, 2, 5]. The corresponding LIS[] would be [INT_MIN, 1, 2, 5](indexes starting from 0). Now we wanna handle 4, i.e., the longest increasing sequence end with 4, we can do a binary search to find the largest integer less than 4. In this case, it should be LIS[2] = 2. Note that the LIS[] should always be an increasing sequence so we can do binary search. Now we got a sequence of length 3 end with 4, so we can update LIS[3] = min(LIS[3], 4). However, if the number we are handling is 7 instead of 4, we get a sequence of length 4 end with 7, which is longer than any existing sequence, then we can simply append the new value to the tail of LIS[]. We can generalize that the new LIS[] will still be increasing sequence. After handled all the integers, the size of LIS[] - 1 would be the desired result.

    class Solution {
    public:
        int binsearch(vector<int>& LIS, int val) {
            int l = 0, r = LIS.size();
            while (l < r - 1) {
                int m = (l + r) / 2;
                if (LIS[m] < val)
                    l = m;
                else
                    r = m;
            }
            return l;
        }
        int lengthOfLIS(vector<int>& nums) {
            vector<int> LIS;
            LIS.push_back(INT_MIN);
            for (int i = 0; i < nums.size(); ++i) {
                int l = binsearch(LIS, nums[i]);
                if (l + 1 == LIS.size())
                    LIS.push_back(nums[i]);
                else
                    LIS[l + 1] = min(LIS[l + 1], nums[i]);
            }
            return LIS.size() - 1;
        }
    };

Log in to reply
 

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