Subsecuencia creciente más larga con suma máxima
Dado un arreglo de
n enteros, se te pide encontrar la subsecuencia creciente más larga de dicho arreglo. Si existen varias subsecuencias con esta misma longitud, puedes imprimir cualquiera de ellas.Una subsecuencia de un arreglo se obtiene eliminando algunos (posiblemente cero) elementos del arreglo, sin alterar el orden de los que quedan. Por ejemplo, si el arreglo es , entonces es una subsecuencia de , pero no lo es, puesto que no se preserva el orden original de los elementos.
💡
Una subsecuencia creciente de un arreglo es aquella cuyas elementos están en orden creciente. Por ejemplo, si el arreglo es , entonces es una subsecuencia creciente de , pero no es subsecuencia creciente de , porque los elementos no están en orden creciente.
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ 1000), que representa la longitud del arreglo.La segunda línea contiene
n enteros separados por espacio (), que son los elementos del arreglo.Salida
El programa debe imprimir la suma de la subsecuencia creciente más larga que tenga la suma máxima.
Entrada | Salida |
8
1 3 2 4 5 2 6 5 | 19 |
6
10 9 2 5 3 7 | 14 |
Explicación
- En el primer ejemplo, la subsecuencia creciente más larga con suma máxima es .
- En el segundo ejemplo, la subsecuencia creciente más larga con suma máxima es .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB