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

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

Un exercice classique : trouver la sous-séquence de plus grande somme.

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.