Giocare a un gioco di rimozione di numeri
Giochiamo a un gioco. Ti vengono forniti
n interi positivi (dove n è pari). A ogni mossa puoi rimuovere un numero dall'inizio o dalla fine della sequenza e tenerlo per te. Io (il computer) rimuoverò l'elemento più grande tra il primo e l'ultimo della sequenza. Se il primo e l'ultimo sono uguali, rimuoverò il primo. Procederemo a turni finché la lista non sarà vuota.Se sei tu a iniziare, qual è la somma massima che puoi raccogliere?
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 1000).La riga successiva contiene
n interi separati da spazio (1 ≤ ≤ ).Output
Il programma deve stampare la somma massima che puoi raccogliere.
Esempi
Ingresso | Uscita |
4
3 2 10 4 | 13 |
Spiegazione
- Prendi il primo 3 →
2 10 4
- Il computer prende il 4 →
2 10
- Prendi il 10 →
2
- Il computer prende il 2 ⇒ Hai raccolto 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB