by hansang:

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int a[N], f[2][N], s[N];
int main(){
    int n; scanf("%d", &n); s[0]=0;
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s[i]=s[i-1]+a[i];
    }
    memset(f, 0, sizeof(f));
    int t=0;
    for(int i=n; i>=1; i--){
        t^=1;
        f[t][i]=a[i];
        for(int j=i+1; j<=n; j++){
            f[t][j]=max(s[j]-s[i]-f[t^1][j]+a[i], s[j-1]-s[i-1]-f[t][j-1]+a[j]);
        }
    }
    printf("%d\n", f[t][n]);
    return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int a[N], f[2][N], s[N];
int main(){
	int n; scanf("%d", &n); s[0]=0;
	for(int i=1; i<=n; i++){
		scanf("%d", &a[i]);
		s[i]=s[i-1]+a[i];
	}
	memset(f, 0, sizeof(f));
	int t=0;
	for(int i=n; i>=1; i--){
		t^=1;
		f[t][i]=a[i];
		for(int j=i+1; j<=n; j++){
			f[t][j]=max(s[j]-s[i]-f[t^1][j]+a[i], s[j-1]-s[i-1]-f[t][j-1]+a[j]);
		}
	}
	printf("%d\n", f[t][n]);
	return 0;
}