11568번: 민균이의 계략

https://www.acmicpc.net/problem/11568


$O(n\lg n)$

최장증가부분수열을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, a[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i<n; i++) {
        scanf("%d", &x);
        a[i] = 1e9;
        *lower_bound(a, a + i, x) = x;
    }
    printf("%d", lower_bound(a, a + n, 1e9) - a);
    return 0;
}