최장 증가 부분 수열

서브태스크 $1$에서는 $D_i$를 $i$번째 원소에서 끝나는 최장 증가 부분 수열의 길이라고 정의한다. $A_j<A_i$인 모든 $j<i$를 확인하여 그중 가장 큰 $D_j$에 $1$을 더한다. 그런 $j$가 없으면 $D_i=1$이다. 이전 원소의 인덱스를 함께 저장하면 수열을 복원할 수 있다. 시간 복잡도는 $O(N^2)$이다.

전체 문제에서는 길이가 $k$인 증가 부분 수열이 가질 수 있는 마지막 값의 최솟값을 길이별로 유지한다. $A_i$를 처리할 때 이 값들에서 $A_i$ 이상인 첫 위치를 이분 탐색하여 갱신한다. 같은 값은 길이를 늘릴 수 없으므로 $A_i$보다 큰 첫 위치가 아니라 이상인 첫 위치를 찾아야 한다.

각 길이의 마지막 값과 함께 그 값을 만든 원소의 인덱스를 저장한다. $A_i$가 길이 $k$의 상태를 갱신한다면, 길이 $k-1$의 마지막 원소 인덱스를 $i$의 이전 원소로 기록한다. 마지막에 가장 긴 길이의 마지막 원소부터 이전 인덱스를 따라가고 순서를 뒤집으면 답을 얻는다.

한 케이스의 시간 복잡도는 $O(N\log N)$이고 공간 복잡도는 $O(N)$이다.

Solution written by GPT6