300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

• new solution update 2022.02.18

c++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lis{INT_MIN};
        for(auto n : nums) {
            if(lis.back() < n) {
                lis.push_back(n);
            } else {
                auto it = lower_bound(lis.begin(), lis.end(), n);
                *it = n;
            }
        }
        return lis.size() - 1;
    }
};

c++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> res{INT_MIN};
        for(auto& n : nums) {
            if(res.back() < n) res.push_back(n);
            else *lower_bound(begin(res), end(res), n) = n;
        }
        return res.size() - 1;
    }
};