Subsecuencia creciente más larga 2
Dado un arreglo de n números enteros, se te pide encontrar la subsecuencia creciente más larga de dicho arreglo. Si hay varias subsecuencias con esta misma longitud, puedes devolver cualquiera de ellas.
Una subsecuencia de un arreglo se forma eliminando algunos (posiblemente ninguno) de sus elementos, sin cambiar el orden de los elementos restantes. Por ejemplo, si el arreglo es , entonces es una subsecuencia de . En cambio, no lo es, ya que el orden de los elementos no se conserva.
Entrada
La primera línea de la entrada contiene un único entero n (1 ≤ n ≤ 100 000), que es la longitud del arreglo.
La segunda línea contiene n números enteros separados por espacios (), que representan 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 es .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB