1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>
using namespace std;
int a[1005], sum[1005], dp[1005][1005];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum[i + 1] = sum[i] + a[i];
    }
    for (int l = 1; l <= n; l++)
    for (int s = 0, t = s + l; t <= n; s++, t++)
        dp[s][t] = sum[t] - sum[s] - min(dp[s + 1][t], dp[s][t - 1]);
    cout << dp[0][n] << endl;
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX