Q. Piyush and Nimit are playing a coin game. They are given n coins with values x1, x2 …. xn where ‘n’ is always even. They take alternate terms. In each turn, a player picks either the first coin or the last coin from the row and removes it from the row. The value of coin is received by that player. Determine the maximum value that Piyush can win with if he moves first. Both the players play optimally
Sample Input
4
1 2 3 4
Sample Output
6
Explanation
Piyush will pick the coin 4. Then Nimit can pick either 1 or 3. In both the cases piyush picks coin 2 and wins with a total of 6
in this Nimit can pick either 1 or 3. In both the cases How piyush picks coin 2 only if Nimit picks 1 then piyush have 7 coins as maximim but if Nimit picks 1 then piyush have 6