100M版本（MLE）：

#include <bits/stdc++.h>
using namespace std;

int n, a[5010], f[5010][5010];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) f[i][i] = a[i];
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j=i + len - 1;
            f[i][j] = a[j]-a[i-1] - min(f[i + 1][j], f[i][j-1]);
        }
            
    printf("%d\n", f[1][n]);
    return 0;
}

50M版本：

#include <bits/stdc++.h>
using namespace std;

int n, a[5010], f[5010*5010/2];
int getid(int i,int j)
{
    int st=n,ed=n-(i-1)+1;
    return (ed+st)*(st-ed+1)/2+(j-i+1);
}   
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) f[getid(i,i)] = a[i];
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j=i + len - 1;
            f[getid(i,j)] = a[j]-a[i-1] - min(f[getid(i+1,j)], f[getid(i,j-1)]);
        }
            
    printf("%d\n", f[getid(1,n)]);
    return 0;
}

100M版本（MLE）：

#include <bits/stdc++.h>
using namespace std;

int n, a[5010], f[5010][5010];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) f[i][i] = a[i];
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j=i + len - 1;
            f[i][j] = a[j]-a[i-1] - min(f[i + 1][j], f[i][j-1]);
        }
            
    printf("%d\n", f[1][n]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, a[5010], f[50105010/2];
int getid(int i,int j)
{
int st=n,ed=n-(i-1)+1;
return (ed+st)(st-ed+1)/2+(j-i+1);
}

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) f[getid(i,i)] = a[i];
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++)
{
int j=i + len - 1;
f[getid(i,j)] = a[j]-a[i-1] - min(f[getid(i+1,j)], f[getid(i,j-1)]);
}
printf("%d\n", f[getid(1,n)]);
return 0;

}