## A Harder Game

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are playing a game with Bruce involving coins laid out in a row.

The two players alternate taking coins from either end of the row. The game ends when no more coins remain.

Bruce is a genius and will always play optimally. However, he is nice and will let you make the first move. What is the maximum total value of coins you can take?

#### Input Specification

The first line will contain , the number of coins.
The second and final line of input will contain integers, , the values of the coins.

#### Constraints

For all subtasks, For of points, For of points, #### Output Specification

The maximum total value of coins you can obtain.

#### Sample Input

4
4 4 9 4

#### Sample Output

13

#### Explanation for Sample Output

4 4 9 4

First, you take the left-most coin, with a value of .

4 9 4

Bruce then picks up either remaining coin, both of which have a value of .

9 4

Following this, you pick up the coin with a value of .

4

And Bruce takes the last coin, and the game ends.

Your coins have a total value of , which is the maximum value you can obtain.

The first subtask can be solved in with dynamic programming.
The second subtask uses a greedy algorithm called termity to solve in 