Jugando un juego de eliminar números
Juguemos un juego. Se te dan
n números enteros positivos (donde n es par). En cada turno, puedes quitar un número del principio o del final de la secuencia y quedártelo. Yo (la computadora) eliminaré el número más grande entre el primero y el último elemento de la secuencia. Si esos dos elementos son iguales, entonces quitaré el primero. Iremos alternando hasta que no quede ningún número en la lista.Si eres quien empieza el juego, ¿cuál es la suma máxima de números que puedes obtener?
Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ 1000).La siguiente línea contiene
n números enteros separados por espacio (1 ≤ ≤ ).Salida
El programa debe imprimir la suma máxima que puedes obtener.
Ejemplos
Entrada | Salida |
4
3 2 10 4 | 13 |
Explicación
- Tomas primero el 3 →
2 10 4
- La computadora toma el 4 →
2 10
- Tomas el 10 →
2
- La computadora toma el 2 ⇒ Has acumulado 3 + 10 = 13
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB