Plus longue sous-séquence croissante 1
On vous donne un tableau de
n entiers, et l’objectif est de trouver la plus longue sous-séquence croissante de ce tableau. S’il en existe plusieurs, vous pouvez en renvoyer n’importe laquelle.Une sous-séquence d’un tableau s’obtient en supprimant certains éléments (éventuellement aucun) sans changer l’ordre des éléments restants. Par exemple, si le tableau est , alors est une sous-séquence de , tandis que n’en est pas une, car l’ordre des éléments n’est pas respecté.
💡
Une sous-séquence croissante d’un tableau est une sous-séquence dont les éléments sont en ordre croissant. Par exemple, si le tableau est , alors est une sous-séquence croissante de , tandis que ne l’est pas, car les éléments ne sont pas en ordre croissant.
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 1000), qui représente la taille du tableau.La deuxième ligne contient
n entiers séparés par des espaces (), qui représentent les éléments du tableau.Sortie
Le programme doit afficher la longueur de la plus longue sous-séquence croissante du tableau.
Exemples
Entrée | Sortie |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Explications
- Dans le premier exemple, la plus longue sous-séquence croissante de ce tableau est .
- Dans le deuxième exemple, la plus longue sous-séquence croissante de ce tableau est .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB