数字を取り除くゲームをしよう
ゲームをしてみましょう。
n 個の正の整数 （ここで n は偶数）が与えられています。各ステップで、あなたは数列の先頭または末尾から 1 つの数字を取り除き、それを自分のものにできます。一方、わたし（コンピュータ）は数列の先頭と末尾を比べ、大きい方を取り除きます。もし両方が同じ値なら、先頭の数字を取ります。これを交互に行い、数列が空になるまで続けます。もしあなたが最初に手番を取るとき、最終的に手に入れられる数字の合計の最大値はいくらになるでしょうか？
入力
最初の行には、整数
n (1 ≤ n ≤ 1000) が 1 つ与えられます。次の行には、
n 個の整数 (1 ≤ ≤ ) がスペース区切りで与えられます。出力
あなたが集められる数字の合計の最大値を出力してください。
サンプル
入力 | 出力 |
4
3 2 10 4 | 13 |
解説
- あなたは最初の 3 を取る →
2 10 4
- コンピュータは 4 を取る →
2 10
- あなたは 10 を取る →
2
- コンピュータは 2 を取る ⇒ あなたの合計は 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB