3745 - 오름세

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 로 해결할 수 있다.
$N$이 적당히 크므로 $O(N^2)$ 은 안되고 $O(NlogN)$ 으로 해결해야 한다.

#include <bits/stdc++.h>
using namespace std;

int LIS(vector<int>& arr){
    vector<int> v(1, arr[0]);
    for(int i=1; i<arr.size(); ++i){
        if(v.back() < arr[i]){
            v.push_back(arr[i]);
        } else {
            *lower_bound(v.begin(), v.end(), arr[i]) = arr[i];
        }
    }
    return v.size();
}

int main(){
    int i, n;
    while(~scanf("%d", &n)){
        vector<int> a(n);
        for(i=0; i<n; ++i) scanf("%d", &a[i]);
        printf("%d\n", LIS(a));
    }
    return 0;
}