A clean solution using C++ lower_bound() function


  • 1
    C
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty())
            return 0;
        vector<int> B(1, nums[0]);
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > B.back()) {
                B.push_back(nums[i]);
            }
            else {
                auto it = lower_bound(B.begin(), B.end(), nums[i]);
                *it = nums[i];
            }
        }
        return B.size();
    }

  • 0
    W
    This post is deleted!

  • 0
    G

    can you write some explanations? thx!


Log in to reply
 

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