Subsecuencia Creciente más Larga 1
Dado un arreglo de
n números enteros, se te pide encontrar la subsecuencia creciente más larga del arreglo. Si existen varias subsecuencias iguales en longitud, puedes mostrar cualquiera de ellas.Una subsecuencia de un arreglo se obtiene al eliminar ciertos (posiblemente ninguno) elementos del arreglo, sin modificar el orden de los elementos restantes. Por ejemplo, si el arreglo es , entonces es una subsecuencia de , pero no lo es, ya que el orden de los elementos no se preserva.
💡
Una subsecuencia creciente de un arreglo es aquella en la que los elementos se encuentran en orden creciente. Por ejemplo, si el arreglo es , entonces es una subsecuencia creciente de , pero no lo es, ya que los elementos no están en orden creciente.
Entrada
La primera línea de la entrada contiene un solo número entero
n (1 ≤ n ≤ 1000), que representa la longitud del arreglo.La segunda línea contiene
n números enteros separados por espacio (), que son los elementos del arreglo.Salida
El programa debe imprimir la longitud de la subsecuencia creciente más larga del arreglo.
Ejemplos
Entrada | Salida |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Explicación
- En el primer ejemplo, la subsecuencia creciente más larga del arreglo es .
- En el segundo ejemplo, la subsecuencia creciente más larga del arreglo es .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB