숫자 뽑기 게임

시간 제한1초메모리 제한256 MB

요약

안쪽 수를 하나씩 골라 고른 수와 양옆 수의 합을 얻으며 전체 점수 합계를 최대화합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구간
정답자: 아직 제출이 없습니다

문제

아현이는 건반악기를 다뤄서 손가락 힘을 기르려고 손가락 끝으로 숫자를 뽑는 게임을 한다. 규칙은 다음과 같다.

아현이에게 양의 정수 리스트가 주어진다. 아현이는 리스트의 맨 앞과 맨 뒤를 뺀 나머지 숫자 중 하나를 고를 수 있다. 고른 숫자는 리스트에서 사라지고, 고른 숫자와 그 양옆 숫자의 합만큼 점수가 오른다. 리스트에 숫자가 두 개만 남으면 게임이 끝난다.

리스트가 1 2 3 4 5인 경우를 보자. 아현이가 3을 뽑으면 점수는 $2+3+4=9$ 가 되고 리스트에는 1 2 4 5가 남는다. 이어서 4를 뽑으면 점수는 $9+2+4+5=20$ 이 되고 리스트에는 1 2 5가 남는다.

리스트가 주어졌을 때 아현이가 받을 수 있는 가장 높은 점수를 구하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 $n$ $k_1$ $k_2$ $\ldots$ $k_n$ 형식으로 주어진다. $n$ 은 리스트에 들어 있는 숫자의 개수이고 $3 \le n \le 200$ 이다. 각 정수 $k_i$ 는 $1 \le k_i \le 100$ 을 만족한다. 마지막 줄에는 $0$ 하나만 주어지며, 이 줄을 읽으면 입력이 끝난다.

출력

각 테스트 케이스마다 아현이가 받을 수 있는 가장 높은 점수를 한 줄에 하나씩 출력한다.

예제4

예제 1

입력

5 1 2 3 4 5
5 2 1 5 3 4
6 30 20 40 50 70 60
0

예상 출력

30
31
570

예제 2
입력
```
3 1 1 1
0
```
예상 출력
```
3
```

예제 3

입력

3 100 100 100
3 1 100 1
3 100 1 100
0

예상 출력

300
102
201

예제 4

입력

4 1 2 3 4
4 4 3 2 1
4 1 100 100 1
4 100 1 1 100
0

예상 출력