[ALGOSPOT]LIS

BOJ 에 있는 문제와 동일하다.

최장 증가 부분수열

#include<cstdio>
#include<vector>
#include<algorithm>
#define in(a) scanf("%d",&a);
#define out(a) printf("%d\n",a);
using namespace std;
 
vector<int> lower;
 
int main(){
    int T, n, input; in(T);
    for(int tc = 0 ; tc < T ; tc++){        
        lower.clear();
        in(n);
        for(int i = 0 ; i < n ; i++){
            in(input);
            auto iter = lower_bound(lower.begin() , lower.end() , input);
            if(lower.end() == iter)    lower.push_back(input);
            else *iter = input;
        }
        out(lower.size());
    }
    return 0;
}