aloalgoLine of Coins Game
You are given a line of coins, each with a certain value. Two players take turns picking a coin from either end of the line. The player with the highest total value at the end wins. Assuming both players play optimally, determine the maximum value the first player can achieve.
Example 1
[3, 2, 2, 3]
5
If Player 1 picks 3 from the left, coins become [2, 2, 3]. Player 2 picks 3 from the right (to maximize their own score), coins become [2, 2]. Player 1 picks 2, coins become [2]. Player 2 picks 2. P1 total: 3+2=5. P2 total: 3+2=5. If Player 1 picks 3 from the right, coins become [3, 2, 2]. Player 2 picks 3 from the left, coins become [2, 2]. Player 1 picks 2, coins become [2]. Player 2 picks 2. P1 total: 3+2=5. P2 total: 3+2=5. In both cases, Player 1 gets a maximum of 5.
Example 2
[5, 3, 7, 10]
15
If Player 1 picks 10 (right), coins become [5, 3, 7]. Player 2 faces [5, 3, 7]. P2 picks 7 (right), coins become [5, 3]. P1 faces [5, 3]. P1 picks 5 (left), coins become [3]. P2 faces [3]. P2 picks 3. P1 total: 10 + 5 = 15. P2 total: 7 + 3 = 10. (Other optimal choices for P1 would lead to a lower score.)
Example 3
[10, 20]
20
Player 1 picks 20. Coins become [10]. Player 2 picks 10. Player 1's total is 20.
[3, 2, 2, 3]
5