## A Harder Game

View as PDF

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

Author:
Problem type

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.

#### Output Specification

The maximum total value of coins you can obtain.

4
4 4 9 4

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.