$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; }
댓글 없음 :
댓글 쓰기