## A Game

There 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)

9 4

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.

### Input

N <= 1000, the number of coins.N lines, each with the value of a coin.

### Output

Your maximum possible score, provided that you go first and your friend plays perfectly.
All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Jun 27, 2013

**Problem Types:**[Show]

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Serene17on Mar 30, 2015 - 8:47:40 pm UTC Clarify plissIs it like the game of nim where your friend is thinking ahead all the way to the end?

fifimanon Mar 30, 2015 - 11:18:40 pm UTC Re: Clarify plissjimgaoon Jan 26, 2015 - 8:47:09 pm UTC BFS?jimgaoon Jan 26, 2015 - 9:11:37 pm UTC Re: BFS?sigkillon Jan 27, 2015 - 5:03:26 am UTC Re: BFS?That being said, you are making a mistake in your BFS that will come back to bite you in other problems. Specifically, you are storing far, far more state than necessary in your queue. You can in fact store the problem state in two integers, whereas your code is storing as many as 1003 integers plus the overhead of a linked list.

If you can figure out how to store the state more compactly, it might push you towards a more sane solution.

jimgaoon Jan 27, 2015 - 6:50:47 pm UTC Re: BFS?Thanks. :D

wangzilv1998on Apr 10, 2014 - 5:16:38 pm UTC Clarificationfifimanon Apr 11, 2014 - 2:10:34 am UTC Re: Clarification