Overview

We treat this as a two-player zero-sum game where players alternately take one card from either the left or right end, and use interval DP to find the maximum value of “first player’s score − second player’s score.”

Analysis

This game involves both “maximizing your own score” and “not leaving cards that benefit your opponent.” Since both players play optimally, simple greedy strategies like “always take the larger card” do not work (because doing so might leave advantageous cards for the opponent in subsequent turns).

Additionally, at each turn there is a choice of taking from the left or right end. A brute-force search of all possibilities would result in \(2^N\) branches, which is far too slow for \(N \le 3000\).

The key insight is that this game can be formulated as maximizing the zero-sum value (first player’s score − second player’s score).
If we define the DP state as “the difference (myself − opponent) that the current player can achieve by playing optimally on the remaining interval,” then when the turn passes to the opponent, the difference flips sign, yielding a clean recurrence.

Algorithm

Let the card sequence be \(V_0, V_1, \dots, V_{N-1}\) (0-indexed).

State Definition

When the cards in interval \([l, r]\) (inclusive on both ends) remain, and the current player plays optimally, define

\[ dp[l][r] \]

as the maximum value of “(current player’s total score) − (opponent’s total score).”

Transition

The current player can choose to take either the left end \(V_l\) or the right end \(V_r\).

• If the left end is taken, the opponent then maximizes “opponent − current player” on interval \([l+1, r]\). That value is \(dp[l+1][r]\), so from the current player’s perspective, the difference is

\[ V_l - dp[l+1][r] \]

• Similarly, if the right end is taken:

\[ V_r - dp[l][r-1] \]

Therefore, the recurrence is

\[ dp[l][r] = \max\bigl(V_l - dp[l+1][r],\; V_r - dp[l][r-1]\bigr) \]

Base Case

When the interval has length 1, the player simply takes that single card:

\[ dp[l][l] = V_l \]

Answer

Since the first player (Takahashi) starts with the full interval \([0, N-1]\), the answer is

\[ dp[0][N-1] \]

Compression to 1D DP (as in the submitted code)

The 2D approach requires \(O(N^2)\) memory, but the transition only needs values from “intervals one length shorter.”
So we store “\(dp[l][r]\) for the current interval length” as simply \(dp[l]\):

• Loop over interval length length from 2 to N
• dp[l+1] has not yet been updated, so it represents \(dp[l+1][r]\)
• dp[l] has not yet been updated, so it represents \(dp[l][r-1]\)

The update uses this correspondence (left = v[l] - dp[l+1], right = v[r] - dp[l] in the code).

Complexity

• Time complexity: \(O(N^2)\) (each interval \([l,r]\) is computed exactly once)
• Space complexity: \(O(N)\) (only a 1D DP array)

Implementation Notes

• Values can be as low as \(-10^9\), but the recurrence still works correctly as-is (since we manage everything as “differences”).

• In the 1D DP compression, the update order is crucial. By iterating l from small to large, dp[l+1] remains in its “pre-update (= previous length)” state, allowing correct computation.

• For \(N=3000\), the input/output can be fairly large, so it is safer to read all input at once using sys.stdin.buffer.read().

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    v = data[1:1+n]

    dp = v[:]  # dp[l] = best (current player - other) for subarray [l..r] with current length
    for length in range(2, n + 1):
        end = n - length
        for l in range(end + 1):
            r = l + length - 1
            left = v[l] - dp[l + 1]
            right = v[r] - dp[l]
            dp[l] = left if left > right else right

    print(dp[0])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.