CSES 1097 / DP

/***
 created: 2022-08-09-21.49.04
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'


ll dp[5005][5005];
ll a[5005],n;

ll solve(ll i,ll j)
{

    if(i==j) return a[i];

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

    ll ans=-1e17;

    ans=a[i]-solve(i+1,j);
    ans=max(ans,a[j]-solve(i,j-1));

    return dp[i][j]=ans;

}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    ll tot=0;

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

    memset(dp,-1,sizeof dp);

    ll ans=solve(0,n-1);

    ans=(ans+tot)/2;

    cout<<ans<<nl;

    get_lost_idiot;
}