N root(n) Solution using patience sort


#1

int Solution::lis(const vector &A) {
… int n=A.size();
… if(n==0)return 0;
… vector<stack>dp(n,stack());
… int ans=0;
… for(int i=0;i<n;i++){
… … int x=A[i];
… … for(int j=0;j<n;j++){
… … … if(dp[j].empty()){
… … … … dp[j].push(x);
… … … … break;
… … … }
… … … if(dp[j].top()>=x){
… … … … dp[j].push(x);
… … … … break;
… … … }
… … }
… }
… for(int i=0;i<n;i++){
… … if(dp[i].empty())break;
… … ans++;
… }
… return ans;
}