Farewell

처음에 $i$번째였던 원소를 마지막까지 남긴다고 하자. 그 원소의 왼쪽에서는 $i-1$개가 삭제되고, 오른쪽에서는 $N-i$개가 삭제된다. 따라서 마지막 값은 삭제 순서와 관계없이

$$A_i-(i-1)+(N-i)=A_i+N+1-2i$$

이다.

모든 위치 $i$에 대해 이 값을 계산하고 최댓값을 구한다. 원소를 입력받을 때 바로 계산하여 현재까지의 최댓값만 저장하면 된다. 한 케이스의 시간 복잡도는 $O(N)$, 추가 공간 복잡도는 $O(1)$이다.

증명

하나의 원소를 끝까지 남기는 동안 다른 원소들과의 상대적인 순서는 변하지 않는다. 처음에 그 원소의 왼쪽에 있던 원소는 삭제될 때 그 값을 $1$ 감소시키고, 오른쪽에 있던 원소는 삭제될 때 그 값을 $1$ 증가시킨다. 나머지 원소는 각각 정확히 한 번 삭제되므로, 처음 $i$번째였던 원소의 최종 값은 항상 $A_i+N+1-2i$이다.

서브태스크 $1$에서는 현재 수열에서 삭제할 원소를 모두 시도하는 완전탐색으로 가능한 마지막 값을 조사할 수 있다. 수열을 직접 변경한 뒤 재귀 호출에서 돌아올 때 원래대로 복구하면 시간 복잡도는 $O(N!)$, 수열과 재귀 호출에 필요한 공간 복잡도는 $O(N)$이다.

서브태스크 $2$에서는 마지막에 남길 원소를 하나씩 정하고, 다른 각 원소가 삭제될 때의 변화량을 하나씩 더한다. 시간 복잡도는 $O(N^2)$이며, 수열을 저장하므로 공간 복잡도는 이다.