Trouver la plus longue sous-séquence croissante

Étant donné un tableau de n entiers, vous devez trouver la sous-séquence croissante la plus longue de ce tableau. S'il existe plusieurs sous-séquences de longueur maximale, vous pouvez renvoyer n'importe laquelle.
Une sous-séquence d'un tableau s'obtient en supprimant certains (éventuellement zéro) éléments du tableau, sans modifier l'ordre des éléments restants. Par exemple, si le tableau est , alors est une sous-séquence de . En revanche, 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 . En revanche, n'en est pas une, car les éléments ne sont pas dans un ordre croissant.

Entrée

La première ligne de l'entrée contient un entier n (1 ≤ n ≤ 100 000), qui représente la taille du tableau.
La deuxième ligne contient n entiers séparés par des espaces, (), qui sont les éléments du tableau.

Sortie

La première ligne doit contenir un entier k - la longueur de la plus longue sous-séquence croissante du tableau.
La deuxième ligne doit contenir k entiers séparés par des espaces, représentant cette plus longue sous-séquence. Dans le cas où plusieurs réponses sont possibles, vous pouvez renvoyer n'importe laquelle.

Exemples

Entrée
Sortie
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

Remarque

Dans le deuxième exemple, la sous-séquence est également une solution valide de longueur 3.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue