Nlog(N) solution -- 5 lines of code


#1

int Solution::lis(const vector &A) {
set<int> s;
for(int i=0;i<A.size();i++){
if(s.count(A[i])>0) continue;
s.insert(A[i]);
auto itr=s.find(A[i]);
itr++;
if(itr!=s.end()) s.erase(itr);
}
return s.size();
}