Гра на максимум суми - підконтрольний суперник#5866
Зліва направо викладено карток у ряд. На кожній картці написано ціле число. Два гравці по черзі беруть по одній картці, причому можна брати лише крайню ліву або крайню праву картку. Гра закінчується, коли всі картки взяті (доки залишаються картки, гравець змушений зробити один із можливих ходів). Мета гри — зібрати якомога більшу суму чисел, написаних на взятих картках.
Однак незрозуміло, чому в цю гру грають Начальник-Самодур і Підлеглий-Підлиза. Начальник-Самодур може повністю контролювати не лише свої ходи, а й усі ходи Підлеглого-Підлези. Яку максимальну суму може гарантовано зібрати Начальник-Самодур (який, звісно, ходить першим) за одну гру?
У першому рядку задано кількість карток (1 \leq N \leq 2013). У другому рядку через пропуск задано цілих чисел, що не перевищують за модулем 10^3, — значення, написані на картках.
Виведіть єдине ціле число — максимальну суму, яку гарантовано може зібрати Начальник-Самодур (перший гравець).
Приклад 1
Оскільки Начальник-Самодур повністю контролює ходи Підлеглого-Підлези, він може спочатку взяти картку з , наказати «супернику» взяти , потім взяти (у підсумку 3 + 9 = 12), після цього Підлеглий-Підлиза забирає , і так «найсправедливіша» гра завершується.