[CSES] Removal Game

void solve()
{
    ll n;
    cin >> n;

    vll a(n);
    rep(i, n) cin >> a[i];

    vvll dp(n + 1, vll(n + 1, 0LL));
    vvll save = dp;

    rep(i, n) rep(j, n) dp[i][j] = -inf;

    FORR(l, n - 1, 0)
    {
        FOR(r, l, n - 1)
        {
            if (l == r)
            {
                dp[l][r] = a[l];
                save[l][r] = l;
            }
            else
            {
                if (l + 1 < n)
                    dp[l][r] = max(dp[l][r], a[l] - dp[l + 1][r]);
                if (r - 1 >= 0)
                    dp[l][r] = max(dp[l][r], a[r] - dp[l][r - 1]);

                if (l + 1 < n && (dp[l][r] == a[l] - dp[l + 1][r]))
                    save[l][r] = l;
                else
                    save[l][r] = r;
            }
        }
    }

    ll ans = 0LL;
    ll l = 0, r = n - 1, op = 0;
    while (l <= r)
    {
        ll index = save[l][r];
        if (op == 0)
            ans += a[index];

        if (index == l)
            l++;
        else
            r--;

        op = op ^ 1;
    }

    cout << ans << "\n";
}