1A.algo - la plus grande sous-séquence croissante¶

Links: notebook, html, PDF, python, slides, GitHub

Un exercice classique : trouver la plus grande sous-séquence croissante. Celle-ci n’est pas nécessairement un bloc contigü de la liste initiale mais les entiers apparaissent dans le même ordre.

Le point de départ est une liste d’entiers $L=(a_1, ..., a_n)$ . On veut trouver la plus grande liste $l$ d’entiers croissante incluse dans $L$ . Cette liste $l$ n’est pas nécessairement un bloc contigü de la liste $L$ mais les entiers apparaissent dans le même ordre que dans la liste initiale. Ce problème est connu sous le nom LIS: longest increasing sequence. L’algorithme le plus rapide est en $O(n \ln n)$ . Le logarithme est souvent le signe qu’un algorithme utilise la dichotomie. L’objectif de cet exercice est d’écrire un algorithme qui résoud le problème, tout en sachant que le plus performant introduire nécessairement une dichotomie.