Exercices de programmation pour classes préparatoires
Écrire une fonction lis_rapide(lst) qui prend une liste d'entiers et renvoie la longueur de la plus longue sous-séquence strictement croissante. Une sous-séquence est obtenue en supprimant zéro ou plusieurs éléments de la liste sans changer l'ordre des éléments restants.
Contrainte de complexité : la liste 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).
| Appel | Résultat attendu |
|---|---|
| lis_rapide([]) | 0 |
| lis_rapide([10, 9, 2, 5, 3, 7, 101, 18]) | 4 |
Connectez-vous pour soumettre du code.