Taking From Either End
A row of piles holds stones. Two players alternate; on each turn the player takes the pile at either END of the remaining row. Both play to maximise their own total, and both play perfectly.
Print the total the FIRST player ends up with.
Taking the larger end each turn is the obvious rule and it is wrong. On
5 3 4 5 it takes 5, the opponent takes 5, then it takes 4, and the first player
ends with 9. That is correct here by luck. On 1 5 2 taking the larger end takes
2, the opponent takes 5, and the first player ends with 3, while taking 1 first
also ends at 3, so the greedy survives. Try 3 9 1 2: greedy takes 3, opponent
takes 9, and the first player ends with 3 + 2 = 5 where the answer is 11.
The reason greedy fails is that a move changes what the OPPONENT can do, and the opponent is not a passive obstacle.
The state is the remaining range, and the key move is to think in terms of the whole range rather than of two separate scores:
best(i, j) = the most the player about to move can take from piles i..j
best(i, j) = total(i, j) - min( best(i+1, j), best(i, j-1) )
Whatever this player leaves, the opponent will then take best of it. So this
player gets the range total minus the opponent's best from what remains, and
chooses the end that leaves the opponent the LEAST.
That single line replaces tracking two players' scores separately, which is where most attempts get tangled.