Độ phức tạp thời gian: ~O(N^2)~.

Gọi ~dp[i][j]~ là điểm tối ưu cho Jiro ~(X-Y)~ trong đoạn ~[i,j]~. Từ đó, ta có thể thêm ~a_i~ vào bên trái của đoạn, hoặc ~a_j~ vào bên phải của đoạn. Khi ta có cách chuyển đổi trạng thái như sau.

$$dp[i][j] = max_{j>i}\begin{cases} a_i−dp[i+1][j] \\ a_j−dp[i][j−1]\\ \end{cases}$$

Lí do ta có cách chuyển đổi trạng thái như vậy là vì khi giải bài toán trên một đoạn ~[i,j]~ bất kì nếu như chọn phần tử ~a[i]~ thì ta giải bài toán trên đoạn ~[i+1,j]~ cho đối thủ mà kết quả tối ưu cho bài toán này là ~-dp[i+1][j]~ do vai trò lúc này hai người chơi hoán đổi cho nhau. Tương tự với khi chọn phần tử ~a[j]~.

Trạng thái ban đầu là ~dp[i][i] = a_i~ vì chỉ có duy nhất một thao tác được thực hiện cho đoạn độ dài ~1~.

#include <bits/stdc++.h>

using namespace std;

long long dp[3001][3001];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int& x : a) cin >> x;

    for (int i = 0; i < n; ++i) dp[i][i] = a[i];

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; ++j)
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);
    cout << dp[0][n - 1] << '\n';
}