Informatica Online Judge

  수열 조작 [2193 / 0891]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 7   Total Tried : 8


The Champion of this Problem (C++) : gs15120 - 0ms / 439byte
My Best Submission (C++) : N/A

[AtCoder]

Background

길이가 $N$인 수열 $a_{1}, a_{2}, ... , a_{N}$ 을 가지고 있다.

이 수열의 길이가 1일 될 때까지 다음 작업을 반복한다.

================================[작업]========================================

- 우선, 수열의 요소 중 하나를 선택한다.

- 만약 그 요소가 양 끝의 원소 중 하나라면 선택한 원소를 삭제한다.

- 양 끝의 원소가 아니라면 선택한 원소를 그 원소의 왼쪽과 오른쪽 두 원소의 합으로 바꾸고 왼쪽과 오른쪽 두 원소는 삭제한다.
=============================================================================

이 작업의 결과 마지막 1개의 원소가 남을 때, 이 원소의 값을 최대화 하고자 한다.

Input

입력 형식은 다음과 같다.

$N$
$a_{1}$ $a_{2}$ ... $a_{N}$

[입력값의 정의역]

$2≤N≤1,000$
|$a_i| ≤ 10^{9}$

[Sub-Task Info]
#1 : $N≤10$ (20%)
#2 : 추가제한 없음 (80%)

Output

구한 최댓값을 출력한다.

IO Example

입력
5
1 4 3 7 5

출력
11

* 설명 :

- 첫 번째 선택 위치 (1) 원소를 선택한다.

4 3 7 5

- 두 번째로 위치 (4) 원소를 선택한다.

4 3 7

- 마지막으로 위치 (2) 원소를 선택한다.

11 (4+7)

이 때 11을 구할 수 있으며 이보다 더 큰 값을 구할 수 있는 경우는 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]