Algorytmy 2
Gra w usuwanie
Dana jest lista $n$ liczb i dwóch graczy, którzy wykonują ruchy naprzemiennie. W każdym ruchu gracz usuwa pierwszą lub ostatnią liczbę z listy, a jego wynik zwiększa się o tę liczbę. Obaj gracze starają się maksymalizować swoje wyniki. Jaki jest maksymalny możliwy wynik pierwszego gracza, gdy obaj gracze grają optymalnie?
Wejście
Pierwszy wiersz wejścia zawiera liczbę $n$. Drugi wiersz wejścia zawiera ciąg $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$.
Wyjście
Pierwszy i jedyny wiersz wyjścia zawiara maksymalny wynik dla pierwszego gracza.
Ograniczenia
- $1 \le n \le 5000$
- $-10^9 \le a_i \le 10^9$
Przykłady
Wejście 1
4
4 5 1 3
Wyjście 1
8