Subsequência Crescente Mais Longa 1
Dado um array de
n inteiros, o objetivo é encontrar a subsequência crescente mais longa desse array. Se houver várias subsequências com o mesmo comprimento, podes devolver qualquer uma delas.Uma subsequência de um array obtém-se removendo alguns (possivelmente zero) elementos do array sem alterar a ordem dos elementos restantes. 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 foi preservada.
💡
Uma subsequência crescente de um array é aquela em que os elementos estão em ordem crescente. 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 ≤ 1000), que representa o comprimento do array.A segunda linha contém
n inteiros separados por espaços (), correspondendo aos elementos do array.Saída
O programa deve imprimir o comprimento da subsequência crescente mais longa do array.
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 subsequência crescente mais longa do array é .
- No segundo exemplo, a subsequência crescente mais longa do array é .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB