11722번: 가장 긴 감소하는 부분 수열

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


$O(n\lg n)$

수열의 각 항에 -1을 곱하고 최장증가수열을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[1000], sz, x, n;
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d", &x);
        int p = lower_bound(dp, dp + sz, -x) - dp;
        dp[p] = -x;
        if (p == sz) sz++;
    }
    printf("%d", sz);
    return 0;
}