このゲームでは左右の端から取り合っていくため、ゲームの途中の状態としては元のカードの配列の連続部分列のみです。

ここで、以下の動的計画法を考えます。 区間 \([l,r]\) のカードでゲームを始めてこの問題と同様の条件で先手と後手が動くときに得られる (先手の得点) \(-\) (後手の得点) 値を持つとします。 このとき、次の手番に移るときに相手にとっては差の正負を反転させるだけでよいです。

先ほど区間 \([l,r]\) について考えた値を\(\text{dp}[l][r] \) とします。

このとき、\(\text{dp}[i][i]=V_i\) です。

\(r-l \geq 1\) の時は、

左端を取ると次は相手が区間 \([l+1,r]\) で最大化して差が \(dp[l+1][r]\) になるため、この手番の視点からでは \(V_l-\text{dp}[l+1][r]\) になります。 右端の場合も同様にして \(V_r-\text{dp}[l][r-1]\) になります。

よって遷移は以下のようになります。

\(\text{dp}[l][r]=\max(V_l-\text{dp}[l+1][r],V_r-\text{dp}[l][r-1])\)

これを \(r-l\) の値が小さい順に計算を行っていくことで求められます。時間計算量は \(\mathrm{O}(N^2)\) です。

実装例C(++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> v(n);
    for (auto& e : v) cin >> e;
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for (int i = 0; i < n; ++i) dp[i][i] = v[i];
    for (int sz = 1; sz < n; ++sz) {
        for (int i = 0; i < n; ++i) {
            int j = i + sz;
            if (j >= n) break;
            dp[i][j] = max(v[i] - dp[i + 1][j], v[j] - dp[i][j - 1]);
        }
    }
    cout << dp[0][n - 1] << endl;
}