7570번: 줄 세우기

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


$O(n)$

1씩 증가하는 최대 길이의 부분 수열을 제외한 수들을 앞, 뒤로 보낸다.
ex)
5 2 4 1 3
<2,3>을 제외한 나머지 수들을 앞, 뒤로 보내야 한다.

#include<cstdio>
int r, n, a[1000001];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i<n; i++) {
        scanf("%d", &x);
        a[x] = a[x - 1] + 1;
        if (a[x]>r) r = a[x];
    }
    printf("%d", n - r);
    return 0;
}