O(NlogN) time and O(N) space solution


#1
int Solution::lis(const vector<int> &A) {
    vector<int> ans;
    ans.push_back(A[0]);
    for(int i=1;i<A.size();i++){
        auto it=lower_bound(ans.begin(),ans.end(),A[i]);
        int ind=it-ans.begin();
        if(ind>=ans.size())
            ans.push_back(A[i]);
        else
            ans[ind]=A[i];
    }
    return ans.size();        
}

#2

Your solution isn’t of order O(NlogN). It’s O(N^2). Because ur vector isn’t sorted