Removal Game

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007;

#define got cout<<"YES\n"; return;
#define got0 cout<<"YES\n"; return 0;

#define bhak cout<<"NO\n"; return;
#define bhak0 cout<<"NO\n"; return 0;

#define bas cout<<"\n";

ll getAns(ll i, ll j, ll n, bool picked, vector<ll> &vec, vector<vector<vector<ll>>> &dp){
    if(i>j){
        return 0;
    }

    if(dp[i][j][picked]!=-1){
        return dp[i][j][picked];
    }

    if(picked){
        ll pickFirst = vec[i] + getAns(i+1, j, n-1, false, vec, dp);
        ll pickLast = vec[j] + getAns(i, j-1,n-1, false, vec, dp);
        return dp[i][j][picked] = max(pickLast, pickFirst);
    }

    ll pickFirst = getAns(i+1, j, n-1, true, vec, dp);
    ll pickLast = getAns(i, j-1, n-1, true, vec, dp);

    return dp[i][j][picked] = min(pickFirst, pickLast);
}

ll getAnsOpt(vector<ll> &vec){
    ll n = vec.size();
    vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>> (n+1, vector<ll> (2, 0)));

    for(ll i=0; i<=n; ++i){
        for(ll j=0; j<i; ++j){
            for(ll k=0; k<2; ++k){
                dp[i][j][k]=0;
            }
        }
    }

    for(ll i=0; i<n; ++i){
        for(ll j=n-1; j>i; --j){
            for(ll k=0; k<2; ++k){
                if(k==1){
                    dp[i][j][k] = max(vec[i] + dp[i+1][j][0], vec[j] + dp[i][j-1][0]);
                }
                else{
                    dp[i][j][k] = min(dp[i+1][j][1], dp[i][j-1][1]);
                }
            }
        }
    }

    return dp[0][n-1][1];
}

int main() {
    // your code goes here
    ll n; cin>>n;
    vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>> (n+1, vector<ll> (2, -1)));
    vector<ll> vec(n);

    for(ll i=0; i<n; ++i){
        cin>>vec[i];
    }

    // ll ans = getAns(0, n-1,n, true, vec, dp);
    ll ans = getAnsOpt(vec);
    cout<<ans;

    return 0;
}