\(N\)개의 동전이 일렬로 놓여 있고 값은 \(a_1, \dots, a_N\)이다. 두 명이 번갈아 진행하며 당신이 먼저 시작한다. 각 차례에 현재 플레이어는 남아 있는 동전 중 가장 왼쪽 또는 가장 오른쪽 동전을 가져가 그 값을 얻는다. 두 플레이어 모두 자신의 총합을 최대화하려 한다. 두 사람이 모두 최적으로 플레이할 때 당신(선공)이 얻는 총 값을 출력하시오.

첫 줄에 \(N\) (\(1 \le N \le 60\))이 주어진다. 둘째 줄에 \(N\)개의 정수 \(a_i\) (\(1 \le a_i \le 1000\))가 주어진다.

선공이 얻는 총 값을 출력한다.

riseoj 작성

출처 RiseOJ Basics