Coin Game — Pick from Either Corner (Optimal Play)

Problem Statement

Two players, A and B, play a coin game. There's a row with an even number of coins, each with a value. Players alternate turns. On each turn, a player picks a coin from either the left or right corner of the remaining row.

Player A (younger) moves first. Both players play optimally to maximize their own total value. The player with more total value wins.

Determine the maximum value Player A can guarantee (and whether A can always win/tie).

Constraints

• 2 <= n <= 1000 (n is even)
• 1 <= coins[i] <= 10^4
• Both players play optimally

Example

Input: coins = [5, 3, 7, 10]

Output: 15

Explanation: A picks 10 (right). B picks 7 (right). A picks 5 (left). B picks 3. A gets 10+5=15, B gets 7+3=10. A wins.

What the Interviewer Expects

1. Recognize it's a minimax DP problem — each player maximizes their own gain, which means minimizing the opponent's.
2. State: dp[i][j] = max value the current player can collect from the subarray coins[i..j].
3. Transition: current player picks either coins[i] or coins[j], then the opponent plays optimally on the rest:
   • dp[i][j] = max(coins[i] + (sum(i+1..j) - dp[i+1][j]), coins[j] + (sum(i..j-1) - dp[i][j-1]))
   • Or the cleaner formulation: dp[i][j] = max(coins[i] - dp[i+1][j], coins[j] - dp[i][j-1]) (relative score)
4. Known result for even coins — the first player can ALWAYS guarantee a win or tie (pick all odd-indexed or all even-indexed coins, whichever sum is larger).
5. Fun follow-up — mention the greedy even/odd trick as a way A can never lose.

Follow-ups

1. Why can the first player never lose with an even number of coins? (odd/even index sum trick)
2. What if the number of coins is odd? Does the guarantee still hold?
3. What's the time and space complexity of the DP? Can you optimize space?
4. What if 3 players play in rotation?