Сэм и хранилище

Задачу можно решить, используя метод динамического программирования. Пусть $$$dp[i]$$$ — ответ на задачу, если игра происходит на массиве $$$a[i \dots n]$$$, а $$$dp[n + 1] = 0$$$. Тогда $$$dp[i] = \max\limits_{j = i}^{n} a[j] - dp[j + 1]$$$. Таким образом, мы получили решение за $$$O(n^2)$$$. Теперь заметим, что значения $$$(a[j] - dp[j + 1])$$$, из которых мы выбираем максимум, не зависят от $$$i$$$, а значит не меняются при уменьшении $$$i$$$. Поэтому, можно сохранять эти значения в какой-нибудь структуре данных, и потом вычислять значение $$$dp[i]$$$, найдя максимум среди сохраненных значений на отрезке $$$[i, n]$$$. Заметим, что мы всегда находим максимум на префиксе, длина которого каждый раз увеличивается на $$$1$$$. Поэтому вместо структуры данных, можно просто поддерживать максимум из значений.