A Harder Game

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Kirito

Problem type

You are playing a game with Bruce involving $N$ ~N~ 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 $N$ ~N~, the number of coins.
The second and final line of input will contain $N$ ~N~ integers, $A_1, A_2, \dots, A_N$ ~A_1, A_2, \dots, A_N~, the values of the $N$ ~N~ coins.

Constraints

For all subtasks:

$1 \le A_i \le 1\,000$ ~1 \le A_i \le 1\,000~

Subtask 1 [40%]

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~

Subtask 2 [60%]

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

Output Specification

The maximum total value of coins you can obtain.

Sample Input

4
4 4 9 4

Sample Output

Explanation for Sample Output

4 4 9 4

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

4 9 4

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

9 4

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

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

Your coins have a total value of $4 + 9 = 13$ ~4 + 9 = 13~, which is the maximum value you can obtain.

Comments

4

Beautiful_Times commented on Nov. 5, 2017, 6:51 p.m. ← edited →

Can anybody tell me why im getting wrong answer?

15

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

The first subtask can be solved in $\mathcal O(N^2)$ ~\mathcal O(N^2)~ with dynamic programming.

The second subtask uses a greedy algorithm called termity to solve in $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~