CSES – Removal Game

#include<bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 5005;
int n,dp[maxn][maxn];
vector<int> v,pre;
//
int sum(int L,int R){
    return pre[R] - pre[L-1];
}
int solve(int L,int R){
    if(L == R) return v[L];
    if(dp[L][R] != -1) return dp[L][R];
    return dp[L][R] = max(sum(L+1,R) - solve(L+1,R) + v[L],
                          sum(L,R-1) - solve(L,R-1) + v[R]);
}
signed main(){
    fastio;
    cin>>n;
    v.push_back(0);
    pre.push_back(0);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++){
        int x; cin>>x;
        v.push_back(x);
        pre.push_back(pre.back() + x);
    }
    cout<<solve(1,n)<<"\n";
    return 0;
}