[C++] Clean O(nlogn) code using binary search


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

  • 0
    B

    Is this correct? Should we preserve the order in the original sequence?


  • 0
    W

    This method can ONLY give the longest "size". If you are asked to retrieve the LIS (the subsequence), you'll need another array/vector to keep more information.


  • 0
    T

    This is brilliant! Always replace with smaller current element cause it may have chance to get longer LIS, but worth to mention that LIS vector does not necessarily contain the real LIS element at the end.


  • 0
    B

    Sorry, I still a bit confused, I thought the question is asking the "subsequence". In your code, it looks like a sorting algorithm...
    I think I got it, sorry for confusing, nice code~


Log in to reply
 

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