I did not understand what the question was asking exactly during the contest. I came up with multiple solutions based on what I thought was being asked, but they were all incorrect. Looks like I finally understood it. I wanted to clarify the question for people who may be confused like me.
The setup should be easy to understand. p1 and p2 take turns in picking a number from the input array, either the first item or the last item. When an item is picked by one of the player, that item cannot be used anymore; you can imagine it being removed from the array.
What made me confused was the part "... predict whether player 1 is the winner. You can assume each player plays to maximize his score." I was not sure what maximizing the score meant. Here is what it means.
Let's say the initial array is [1, 5, 2]. It's p1's turn. p1 will pick either 1 or 2, but it wants to make sure that whichever one he picks will maximize his gain at the end. What if p1 picks 1? Now the array is [5, 2] and it's p2's turn to pick. p2 looks at the current array and thinks about how to maximize his gain at the end. Obviously, picking 5 will maximize his gains. So, p2 will pick 5, leaving 2 for p1. Resulting scores for p1 and p2 are 3 and 5 respectively. This one did not work out for p1.
What if p1 picks 2 at the beginning? Then the array becomes [1, 5]. Again, p2 looks at the current array and thinks about how to maximize his gain at the end. Picking 5 will maximize his gains. So, p2 will pick 5, leaving 1 for p1. Resulting scores for p1 and p2 are 3 and 5 respectively. This one did not work out for p1 either. Those were the only two possibilities for game play. p1 can never win.
What if the input array is [1, 5, 233, 7]? For this one, let me list all possibilities and explain which ones are valid and which ones are not.
What clarified the question for me was realizing that in each step the current player takes a look at the current array as a whole and tries to make the best pick for maximizing it's gain (taking into consideration what the other player may do).
I hope this helps someone.
... predict whether player 1 is the winner. You can assume each player plays to maximize his score.
For short: they are both as smart as alphaGo.Therefore there is actually only one possible path in this decision tree.