Overview

This is a classic interval DP problem where \(N\) cards are arranged in a row on a table, and two players alternately take cards from either the left end or the right end. We need to find the score difference when both players play optimally.

Analysis

Key Observation

In this game, since only the “left end” or “right end” can be taken each turn, the cards remaining on the table at any point always form a contiguous subsequence (interval) of the original sequence. This is the crucial point that allows us to apply interval DP.

Problem with the Naive Approach

Since there are 2 choices (left or right) at each turn, an exhaustive search would result in \(2^N\) branches, which is far too slow for \(N \leq 3000\).

Solution Strategy: Game-Theoretic Interval DP

For the remaining card interval \(V[i..j]\), we define \(dp[i][j]\) as “the current player’s score − the opponent’s score.”

If the current player takes the left end \(V[i]\), the interval \(V[i+1..j]\) remains for the opponent’s turn. The “self − opponent” value for the opponent is \(dp[i+1][j]\), so from the current player’s perspective, the difference becomes \(V[i] - dp[i+1][j]\). Similarly, taking the right end \(V[j]\) gives \(V[j] - dp[i][j-1]\).

The key point here is the sign inversion. Since \(dp[i+1][j]\) represents “the next player’s (i.e., the opponent’s) score − the current player’s score,” we negate it to compute the difference from the current player’s perspective.

Concrete Example

Consider \(V = [4, 1, 3]\).

• \(dp[0][0] = 4,\ dp[1][1] = 1,\ dp[2][2] = 3\) (with only one card, just take it)
• \(dp[1][2] = \max(V[1] - dp[2][2],\ V[2] - dp[1][1]) = \max(1 - 3,\ 3 - 1) = 2\)
• \(dp[0][1] = \max(V[0] - dp[1][1],\ V[1] - dp[0][0]) = \max(4 - 1,\ 1 - 4) = 3\)
• \(dp[0][2] = \max(V[0] - dp[1][2],\ V[2] - dp[0][1]) = \max(4 - 2,\ 3 - 3) = 2\)

Therefore, Takahashi’s score − Aoki’s score \(= 2\).

Algorithm

1. State definition: \(dp[i][j]\) = when the interval \(V[i..j]\) remains, the current player’s score − the opponent’s score (under optimal play)
2. Base case: \(dp[i][i] = V[i]\) (with only one card, the only option is to take it)
3. Transition: Compute in order from shorter intervals to longer ones

\[dp[i][j] = \max(V[i] - dp[i+1][j],\ V[j] - dp[i][j-1])\]

1. Answer: Since Takahashi goes first, \(dp[0][N-1]\) directly gives “Takahashi’s score − Aoki’s score”

Complexity

• Time complexity: \(O(N^2)\) — There are \(O(N^2)\) intervals, and each transition is \(O(1)\)
• Space complexity: \(O(N^2)\) — Size of the DP table

Implementation Notes

• Interval DP must be computed in order from shorter intervals to longer ones. Loop in the order: length 1 → length 2 → … → length \(N\).

• Do not forget the minus sign in \(-dp[i+1][j]\) in the transition formula. Since “self” and “opponent” swap every time the turn changes, we subtract the opponent’s optimal value.

• Since \(V_i\) can take negative values, be careful about data type overflow (in Python, there is no integer overflow).

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    V = [int(input_data[i + 1]) for i in range(N)]
    
    # dp[i][j] = the value of (current player's score - opponent's score)
    # for the subarray V[i..j]
    # When it's a player's turn, they pick left or right to maximize their own total.
    # dp[i][j] = max(V[i] - dp[i+1][j], V[j] - dp[i][j-1])
    
    dp = [[0] * N for _ in range(N)]
    
    for i in range(N):
        dp[i][i] = V[i]
    
    for length in range(2, N + 1):
        for i in range(N - length + 1):
            j = i + length - 1
            dp[i][j] = max(V[i] - dp[i + 1][j], V[j] - dp[i][j - 1])
    
    print(dp[0][N - 1])

main()

---

This editorial was generated by claude4.6opus-thinking.