Subsequência Crescente Mais Longa 2
Dada uma lista (array) com
n inteiros, é solicitado que se encontre a subsequência crescente mais longa dessa lista. Se existir mais de uma subsequência com o mesmo comprimento máximo, pode-se apresentar qualquer uma delas.Uma subsequência de uma lista obtém-se removendo alguns (eventualmente nenhum) dos seus elementos, sem alterar a ordem dos restantes. Por exemplo, se a lista for , então é uma subsequência de . Já não é uma subsequência de , pois a ordem dos elementos não é mantida.
💡
Uma subsequência crescente de uma lista é uma subsequência em que os elementos surgem em ordem crescente. Por exemplo, se a lista for , então é uma subsequência crescente de . Já não é uma subsequência crescente de , pois os seus 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 da lista.A segunda linha contém
n inteiros separados por espaços, (), que representam os elementos da lista.Saída
O programa deve apresentar o comprimento da maior subsequência crescente da lista.
Exemplos
Entrada | Saída |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Explicação
- No primeiro exemplo, a maior subsequência crescente da lista é .
- No segundo exemplo, a maior subsequência crescente da lista é .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB