Optimal First-Player Card Score
Problem statement
Two players play a game with an even-length array cards of positive values. Both players see the full sequence and play optimally.
The players alternate turns, and the first player moves first. On each turn, the current player removes either the leftmost or the rightmost remaining card and adds its value to their score.
Return the final score of the first player.
Function
maxScore(cards: int[]) → longExamples
Example 1
cards = [1,9,10,5,6,4]return = 18Optimal play gives the first player a final score of 18. Any move is evaluated against the opponent's best reply.
Example 2
cards = [4,7,2,9]return = 16The first player takes 9. Whatever end the second player chooses, the first player then takes 7.
Constraints
2 <= cards.length <= 2000cards.lengthis even.1 <= cards[i] <= 10^9- The answer fits in a signed
64-bit integer.