## A Harder Game

View as PDF

Points: 15 (partial)
Time limit: 2.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.

#### 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.

## Comments

• Beautiful_Times  commented on Nov. 5, 2017, 1:51 p.m. edited

Can anybody tell me why im getting wrong answer?

• Kirito  commented on Nov. 5, 2017, 2:37 p.m.

The first subtask can be solved in with dynamic programming.

The second subtask uses a greedy algorithm called termity to solve in