Optimizing greedy solution for choice game
The first player cannot always win – consider the case in which all numbers are the same. But we can always guarantee a draw. Here is the strategy – I'll let you figure out why it works.


  Given the sequence $a_1,\ldots,a_{2n}$, calculate $a_{odd} = a_1 + a_3 + \cdots + a_{2n-1}$ and $a_{even} = a_2 + a_4 + \cdots + a_{2n}$. If $a_{odd} &gt; a_{even}$, always pick odd indices. If $a_{even} &gt; a_{odd}$, always pick even indices. Otherwise, the game is a draw.