C++, O(nlogn) solution

#1 
int binary_search(int x, vector<int> &dp, int l, int r){
    int m;
    
    while(l <= r){
        m = (l + r) / 2;
        
        if(dp[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return l;
}

int Solution::lis(const vector<int> &A) {
    int n = A.size();
    vector<int> dp(n, 0);
    int l = 0, r = 0;
    
    dp[0] = A[0];
    for(int i = 1; i < n; i++){
        int ind = binary_search(A[i], dp, l, r);
        dp[ind] = A[i];
        r = max(r, ind);
    }
    return r + 1;
}