My binary search-based O(n log n) C++ solution


#1
int Solution::lis(const vector<int>& nums) {
    vector<int> dp(nums.size());
    int len = 0;
    for (int num:nums) {
        int i = lower_bound(dp.begin(), dp.begin() + len, num) - dp.begin();
        dp[i] = num;
        len = max(len, i + 1);
    }
    return len;
}