10714번 - 케이크 자르기 2

JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다.

케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i 번째 조각은 i - 1 번째와 i + 1 번째 조각과 인접해있다. (단, 0번째는 N 번째, N + 1 번째는 1번째로 간주한다). i 번째 조각의 크기는 A_i 이지만, 칼질이 서툴러 A_i가 모두 다른 값을 가지게 되었다.

그림 1 : 케이크의 예 (N = 5, A₁ = 2, A₂ = 8, A₃ = 1, A₄ = 10, A₅ = 9)

이 N개를 JOI 군과 IOI 양이 나누기로 하였다. 나누는 방법은 다음과 같다.

1. 먼저, JOI 군이 N 개의 조각 중 원하는 것 하나를 가져간다.
2. 그 뒤, IOI 양으로부터 시작해 IOI 양과 JOI 군은 번갈아가며 남은 조각을 하나씩 가져간다. 단, 인접한 조각 중 하나 이상의 조각이 이미 선택된 경우에만 가져갈 수 있다. 가져갈 수 있는 조각이 여러 개 있을 때엔, IOI 양은 그 중 가장 큰 조각을 가져가고, JOI 군은 원하는 조각을 가져갈 수 있다.

JOI 군은 자신이 가져온 조각들 크기의 합을 최대화하고 싶다.

케이크의 조각 수 N 과, N 개의 조각의 크기에 대한 정보가 주어질 때, JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 구하는 프로그램을 작성하시오.

표준입력으로부터 이하의 입력이 주어진다.

• 첫번째 줄에는 케이크가 N 개의 조각으로 나뉘어 있음을 나타내는 정수 N이 주어진다.
• 이어지는 N 열 중 i 열 (1 ≦ i ≦ N) 에는 i 번째 조각의 크기를 나타내는 정수 A_i가 적혀있다.

모든 입력 데이터는 아래의 조건을 만족한다.

• 1 ≦ N ≦ 2 000．
• 1 ≦ A_i ≦ 1 000 000 000．
• A_i 모두 다른 값을 갖는다.

JOI 군이 가져올 수 있는 조각들의 합계의 최대치를 한 줄로 출력하시오.

JOI 군이 다음과 같은 순서로 케이크를 가져오는 것이 최적해이다.

1. JOI 군이 2번째 조각을 가져온다. 이 조각의 크기는 8이다.
2. IOI 양은 1번째 조각을 가져온다. 이 조각의 크기는 2이다.
3. JOI 군이 5번째 조각을 가져온다. 이 조각의 크기는 9이다.
4. IOI 양은 4번째 조각을 가져온다. 이 조각의 크기는 10이다.
5. JOI 군이 3번째 조각을 가져온다. 이 조각의 크기는 1이다.

최종적으로, JOI 군이 가져온 조각들 크기의 합계는 8+9+1 = 18이 된다.