Encontrar la subsecuencia creciente más larga
Dado un arreglo de
n enteros, se te pide encontrar la subsecuencia creciente más larga de dicho arreglo. Si existen varias subsecuencias de la misma longitud, puedes mostrar cualquiera de ellas.Una subsecuencia de un arreglo se obtiene eliminando algunos (posiblemente cero) elementos del arreglo, sin alterar el orden de los elementos restantes. Por ejemplo, si el arreglo es , entonces es una subsecuencia de , pero no lo es, porque no se conserva el orden de los elementos.
💡
Una subsecuencia creciente de un arreglo es aquella en la que los elementos están en orden ascendente. 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 ascendente.
Input
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ 100 000), la longitud del arreglo.La segunda línea contiene
n enteros separados por espacio (), que representan los elementos del arreglo.Output
La primera línea debe contener un entero
k, que es la longitud de la subsecuencia creciente más larga del arreglo.La segunda línea debe contener
k enteros separados por espacio, que representen la subsecuencia más larga. En caso de haber varias respuestas válidas, puedes mostrar cualquiera de ellas.Examples
Input | Output |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Note
En el segundo ejemplo, la subsecuencia también es una subsecuencia creciente válida de longitud 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB