12738번: 가장 긴 증가하는 부분 수열 3

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


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
int n, a[1000000], sz, x;
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &x);
        int p = std::lower_bound(a, a + sz, x) - a;
        sz += p == sz;
        a[p] = x;
    }
    printf("%d", sz);
    return 0;
}