Google Interview Question 16th Feb 2011

Given N pots arranged in a line. Each pot contains some gold coins. Two players A & B start playing a game in which each player will choose a pot alternatively. The constraint is that they can choose the pots at the beginning of the line or at the end of line (The pot once picked is removed from the line). The player which has more number of coins at the game wins, assuming A starts the game. Both player make optimum choice.
Example
N=4 (5,20, 4,1) --> A wins
N=5 (5,5, 20, 1, 1) --> B wins
N=5  (5 5 20 8 14) --> A wins

N=5  (5 5 20 1 14) --> B wins


Solution