何の話かと言うと
この問題をネタにして、対戦ゲーム（マルコフ決定過程）のちょっとだけ応用的な考え方を説明します。
基本的な考え方については、まずは、こちらの記事をご確認ください。
状態価値関数の一般的な定義
自分の手番の状態 s において、「これ以降に追加で取得できる得点の合計」を dp[s] として、これを状態価値関数と呼びます。
今回のゲームでは、X-Y をこのゲームの「総得点」として、太郎君は、X-Y を最大化する戦略、次郎君は X-Y を最小化する戦略を取ります。
話をわかりやすくするために、N % 2 == 0（Nは偶数）と仮定すると、最後の1要素は次郎君が取るので、A[i] を取るとすると、総得点には -A[i] が加わります。したがって、要素 A[i] だけが残った最終状態 s の状態価値関数は dp[s] = -A[i] となります。
おっと・・・ここで、状態 s の表記方法を決めておきましょう。このゲームでは、残った要素の先頭の番号 i と末尾の番号 j を用いて、ペア (i, j) によって、状態を表すことができます。この場合、状態価値関数は、2次元リストを用いて dp[i][j] と表すことができます。
とりあえず、1要素が残った状態については、次のように計算ができます。
for i in range(1, N+1): dp[i][i] = -A[i]
状態価値関数の遷移
そして、この1つ手前の太郎君の手番を考えると、考え得る状態は、(i, i+1) （i=1,2,...,N-1）となります。それぞれの状態について、dp[i][i+1] はどのように計算できるでしょうか・・・？
太郎君の立場では、i を取るか、i+1 を取るかを決める必要がありますが、仮に i を取ったとすると、まず、得点 A[i] が入り、その後は、先に計算した dp[i+1] が追加されます。つまり、ゲーム終了時までに（総得点X-Yに）追加される得点合計は、A[i] + dp[i+1][i+1] です。同様に、i+1 を取った場合は、A[i+1] + dp[i][i] です。太郎君は、総得点 X-Y が大きくなる方を選ぶはずなので、実際の値は、
dp[i][i+1] = max(A[i] + dp[i-1][i-1], A[i+1] + dp[i][i]) # --- (1)
と決まります。
ではでは、さらにこの1つ手前の次郎君の手番を考えると・・・・、もうだいたいのパターンが読めましたね。考え得る状態は、(i, i+2)（i=1,2,...,N-2）で、それぞれについての状態価値関数は、
dp[i][i+2] = min(-A[i] + dp[i+1][i+2], -A[i+2] + dp[i][i+1]) # --- (2)
です。太郎君の手番と次郎君の手番で遷移ルールが異なるので、残った数列の幅 d を d = 1,2,..., N と変化させながら、d が偶数の場合と奇数の場合で、交互に、(1) と (2) のルールを適用していけばOKです。最後に計算される dp[1][N] が問題の答えとなります。
import sys def main(f): N = int(f.readline()) A = [None] + list(map(int, f.readline().split())) # N は偶数と仮定する dp = [[None] * (N+1) for _ in range(N+1)] # dp[i][j] : 残りが a_i ... a_j の時の状態価値関数、つまり、この後に X-Y に追加できる値 for i in range(1, N+1): # 幅 d = 1 の場合 dp[i][i] = -A[i] for d in range(2, N+1): for i in range(1, N-d+2): j = i + d - 1 if d % 2 == 0: case_l = A[i] + dp[i+1][j] case_r = A[j] + dp[i][j-1] dp[i][j] = max(case_l, case_r) else: case_l = -A[i] + dp[i+1][j] case_r = -A[j] + dp[i][j-1] dp[i][j] = min(case_l, case_r) if N % 2 == 0: print(dp[1][N]) else: # N が奇数だった場合は符号違いを答えればよい print(-dp[1][N]) main(sys.stdin)
これですべてのケースがパスできます。
ちょっとあっさりとした感じですが、一般に、自分のアクションによって状態が変化していくゲーム系の問題では、状態価値関数、つまり、「今の状態 s 以降に追加できる合計得点 dp[s]」を利用するのが定番のテクニックになります。
おまけ（より一般的な状態価値関数の定義）
ここでは、「自分の手番の状態 s において、これ以降に追加で取得できる得点の合計」を状態価値関数と定義しましたが、より一般には、
・自分の手番の状態 s において、これ以降に追加で取得できる得点の合計の最大値
が状態価値関数の定義となります。最後の「最大値」という言葉がミソです。この問題では「最善の手」を選択すると言う前提がありましたが、この定義であれば「最善の手」という概念を使う必要がありません。次に取る手によって、この後に取得できる合計得点はいろいろ変わりますが、その中でも最大の値を採用するという考え方です。
上記で説明した太郎君の立場での dp[i][i+1] の計算は、ちょうどこの定義に当てはまっています。二種類の手のそれぞれで計算して、それらの max を取っていますよね。（太郎君と次郎君で立場が変わりますが、次郎君からは、-dp[ ][ ] が状態価値関数と考えれば辻褄があります。）
もう一つおまけ（区間DPについて）
この問題では、ゲームが進むにつれて数列の幅が減っていくので、A[i] 〜 A[j] という特定の範囲の結果を dp[i][j] として、「範囲の幅」を増やしていく方向に遷移させていきました。このような方法を一般に「区間DP」と呼びます。（個人的には「幅DP」と呼んでいます。）
「一列にならんだ何かを処理する系」の問題で、うまく利用できることが時々あるので、こういう手法があるんだー、という事をちょっと覚えておくとよいでしょう。
