A jogar um jogo de remoção de números
Vamos jogar um jogo. Tens ao teu dispor
n inteiros positivos (sendo n par). Em cada jogada, podes remover um número do início ou do fim da sequência para ficares com ele. Eu (o computador) removo o maior entre o primeiro e o último elemento da sequência. Se estes forem iguais, removo o primeiro. Jogamos alternadamente até que não fiquem mais números na lista.Se fores tu a começar o jogo, qual será a soma máxima de números que consegues acumular?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 1000).A linha seguinte contém
n inteiros separados por espaço (1 ≤ ≤ ).Saída
O programa deve imprimir a soma máxima que podes recolher.
Exemplos
Input | Output |
4
3 2 10 4 | 13 |
Explicação
- Tu retiras o primeiro 3 →
2 10 4
- O computador retira o 4 →
2 10
- Tu retiras o 10 →
2
- O computador retira o 2 ⇒ Ficaste com 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB