题解

#include <stdlib.h>

#define MAX_N 3000

int main() {
    int N;
    long long a[MAX_N];
    long long dp[MAX_N][MAX_N];
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 0; i < N; i++) {
        dp[i][i] = a[i];
    }
    for (int len = 2; len <= N; len++) {
        for (int i = 0; i <= N - len; i++) {
            int j = i + len - 1;
            long long take_i = a[i] - dp[i+1][j];
            long long take_j = a[j] - dp[i][j-1];
            dp[i][j] = (take_i > take_j) ? take_i : take_j;
        }
    }
    printf("%lld\n", dp[0][N-1]);

    return 0;
}