Encontre a Subsequência Crescente Mais Longa
Dado um array de
n inteiros, pretende-se encontrar a subsequência crescente mais longa desse array. Se existirem várias subsequências possíveis com esse comprimento, pode apresentar qualquer uma delas.Uma subsequência de um array é obtida ao remover alguns (possivelmente nenhum) elementos do array, sem alterar a ordem dos que restam. Por exemplo, se o array for , então é uma subsequência de , mas não é uma subsequência de , pois a ordem dos elementos não é preservada.
💡
Uma subsequência crescente de um array é aquela em que os elementos estão em ordem ascendente. Por exemplo, se o array for , então é uma subsequência crescente de , mas não é, pois os elementos não estão em ordem crescente.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 100 000), o comprimento do array.A segunda linha contém
n inteiros separados por espaço (), representando os elementos do array.Saída
A primeira linha deve conter um único inteiro
k - o comprimento da subsequência crescente mais longa do array.A segunda linha deve conter
k inteiros separados por espaço, que representem a subsequência mais longa. Se existirem várias respostas possíveis, pode apresentar qualquer uma delas.Exemplos
Entrada | Saída |
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 |
Nota
No segundo exemplo, a subsequência também é uma subsequência crescente válida de comprimento 3.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB