A GameThere are a bunch of coins on a table, laid out in a straight line.
Each coin has a (positive) value from 1 to 1000. Now, you're going to play a game with a friend.
At every turn, you must remove a coin from one end of the line.
Turns alternate, so your friend goes immediately after you're done.
The game ends when there are no coins remaining.
An example game:
The coins start like this:
4 4 9 4
You always go first, so you take the 4 from the left side:
4 9 4
Your friend takes any of the 4s (it doesn't matter)
Now you can take the 9, and your friend takes the remaining 4.
Your score, in this case, is 4+9 = 13.
(In this case you can always beat your friend.)
Find the maximum possible score you can achieve.
InputN <= 1000, the number of coins.
N lines, each with the value of a coin.
OutputYour maximum possible score, provided that you go first and your friend plays perfectly.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013
- Dynamic Programming
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3