부분 수열 뒤집기

농부 존은 사진을 찍기 위해 \(N\)마리의 소를 한 줄로 세우고 있다 (\(1 \leq N \leq 50\)). 줄에서 \(i\)번째 소의 키는 \(a(i)\)이며, 농부 존은 소들의 줄에 키 순으로 증가하는 긴 부분 수열이 있으면 미적으로 보기 좋은 사진이 될 것이라고 생각한다.

복습하자면, 부분 수열이란 소들의 수열에서 어떤 인덱스들 \(i_1 < i_2 < \ldots < i_k\)에서 뽑은 원소들의 부분집합 \(a(i_1), a(i_2), \ldots, a(i_k)\)이다. \(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\)이면 이 부분 수열이 증가한다고 한다.

FJ는 소들의 배열 안에 긴 증가 부분 수열이 존재하기를 바란다. 이를 보장하기 위해, FJ는 처음에 임의의 부분 수열 하나를 골라 그 원소들을 뒤집는 것을 허용하기로 한다.

예를 들어 다음 리스트가 있을 때

1 6 2 3 4 3 5 3 4

선택한 원소들을

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

뒤집으면 다음을 얻는다.

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

뒤집힌 부분 수열이 처음 차지하던 것과 같은 인덱스들을 그대로 사용하고, 나머지 원소들은 변하지 않는다는 점에 주목하자.

임의의 부분 수열 하나를 한 번 뒤집을 수 있을 때, 만들 수 있는 증가 부분 수열의 최대 길이를 구하시오.

문제 출처: Lewin Gan

문제 출처: Lewin Gan

입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에 \(a(1) \ldots a(N)\)이 주어지며, 각각은 \(1 \ldots 50\) 범위의 정수이다.

최대 한 개의 부분 수열을 뒤집은 뒤 만들 수 있는 최장 증가 부분 수열의 원소 개수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > January > Platinum