1. Идея

Нужно найти, какую максимальную сумму сможет набрать первый игрок, если оба играют оптимально и на каждом ходу берут монету только с одного из концов.

Это типичная игра на отрезке. Состояние удобно задавать так:

• dp[l][r] — максимальная суммарная ценность, которую сможет получить игрок, чей ход сейчас, если на столе остались монеты с индексами от l до r.

Тогда ответом будет dp[0][n - 1].

Главная мысль: если текущий игрок берёт одну из крайних монет, то оставшийся отрезок достаётся сопернику, и он уже оптимально наберёт на нём свою максимальную сумму. Значит, сумма, которую получит текущий игрок с оставшейся части, равна:

• сумма всех монет на оставшемся отрезке
• минус то, что оптимально заберёт соперник.

Это и позволяет записать переход.

2. Наблюдения

Наблюдение 1. Для одного элемента ответ очевиден

Если осталась ровно одна монета a[i], то игрок просто забирает её:

• dp[i][i] = a[i]

Наблюдение 2. Что будет, если взять левую монету

Пусть рассматривается отрезок l..r.

Если текущий игрок берёт левую монету a[l], то дальше остаётся отрезок l + 1 .. r, и ход уже у соперника.

На отрезке l + 1 .. r соперник сможет получить dp[l + 1][r].

Тогда текущему игроку из оставшихся монет достанется:

• сумма отрезка l + 1 .. r
• минус dp[l + 1][r]

Итого при выборе левой монеты:

• a[l] + сумма(l + 1 .. r) - dp[l + 1][r]

Наблюдение 3. Аналогично для правой монеты

Если взять правую монету a[r], то остаётся отрезок l .. r - 1.

Соперник на нём получит dp[l][r - 1], значит текущему игроку из остатка достанется:

• сумма l .. r - 1
• минус dp[l][r - 1]

Итого:

• a[r] + сумма(l .. r - 1) - dp[l][r - 1]

Наблюдение 4. Нужны быстрые суммы на отрезках

Чтобы быстро находить сумму любого подотрезка, строим префиксные суммы:

• pref[i] — сумма первых i элементов

Тогда сумма на отрезке l..r равна:

• pref[r + 1] - pref[l]

Это позволяет считать переход за O(1).

3. Алгоритм

1. Считать n и массив a.
2. Построить массив префиксных сумм pref.
3. Создать таблицу dp размера n x n.
4. Заполнить базу:
   • dp[i][i] = a[i]
5. Перебирать длину отрезка от 2 до n.
6. Для каждого отрезка l..r:
   • посчитать вариант взять слева:
     • take_left = a[l] + sum(l + 1, r) - dp[l + 1][r]
   • посчитать вариант взять справа:
     • take_right = a[r] + sum(l, r - 1) - dp[l][r - 1]
   • взять максимум:
     • dp[l][r] = max(take_left, take_right)
7. Вывести dp[0][n - 1].

4. Почему это работает

Докажем корректность динамики по длине отрезка.

База

Если l = r, на столе одна монета. Игрок, который ходит, забирает её целиком. Значит:

• dp[l][l] = a[l]

Это верно.

Переход

Предположим, что для всех отрезков длины меньше текущей значения dp уже посчитаны правильно. Рассмотрим отрезок l..r.

Игрок, который сейчас ходит, может сделать только два хода:

Вариант 1: взять левую монету

Тогда он сразу получает a[l].

После этого остаётся отрезок l + 1 .. r, и ход переходит сопернику. По определению dp, соперник на этом отрезке оптимально наберёт dp[l + 1][r].

Сумма всех монет на оставшемся отрезке равна sum(l + 1, r). Значит, текущему игроку из этих монет достанется:

• sum(l + 1, r) - dp[l + 1][r]

Итог текущего игрока при таком выборе:

• a[l] + sum(l + 1, r) - dp[l + 1][r]

Вариант 2: взять правую монету

Полностью аналогично:

• текущий игрок получает a[r]
• на отрезке l .. r - 1 соперник заберёт dp[l][r - 1]
• из оставшихся монет текущему игроку достанется sum(l, r - 1) - dp[l][r - 1]

Итого:

• a[r] + sum(l, r - 1) - dp[l][r - 1]

Выбор оптимального хода

Игрок играет оптимально, значит выберет лучший из двух вариантов. Поэтому

• dp[l][r] = max(take_left, take_right)

Мы выразили значение через более короткие отрезки, которые уже корректны по предположению индукции. Значит, и dp[l][r] считается правильно.

Итак, по индукции все значения dp корректны, а значит корректен и ответ dp[0][n - 1].

5. Сложность

Пусть n — количество монет.

• Состояний dp всего n * n
• Для каждого состояния переход считается за O(1)

Итоговая сложность:

• по времени: O(n^2)
• по памяти: O(n^2)

При n <= 1000 это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + a[i];
    }

    auto get_sum = [&](int l, int r) -> long long {
        if (l > r) return 0;
        return pref[r + 1] - pref[l];
    };

    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int i = 0; i < n; i++) {
        dp[i][i] = a[i];
    }

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;

            long long take_left = a[l] + get_sum(l + 1, r) - dp[l + 1][r];
            long long take_right = a[r] + get_sum(l, r - 1) - dp[l][r - 1];

            dp[l][r] = max(take_left, take_right);
        }
    }

    cout << dp[0][n - 1] << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

pref = [0] * (n + 1)
for i in range(n):
    pref[i + 1] = pref[i] + a[i]

dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = a[i]

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1

        sum_left_rest = pref[r + 1] - pref[l + 1]
        sum_right_rest = pref[r] - pref[l]

        take_left = a[l] + sum_left_rest - dp[l + 1][r]
        take_right = a[r] + sum_right_rest - dp[l][r - 1]

        dp[l][r] = max(take_left, take_right)

print(dp[0][n - 1])