Prépa Code Connexion Inscription

Écrire une fonction lis_rapide : int array -> int qui renvoie la longueur de la plus longue sous-séquence strictement croissante d'un tableau d'entiers. Une sous-séquence est obtenue en supprimant zéro ou plusieurs éléments du tableau sans changer l'ordre des éléments restants.

Contrainte de complexité : le tableau peut contenir jusqu'à 100 000 éléments. Une solution en O(n²) dépassera la limite de temps sur les tests cachés — votre solution doit être en O(n log n).