.. _td1aplusgrandesommerst:

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


.. only:: html

    **Links:** :download:`notebook <td1a_plus_grande_somme.ipynb>`, :downloadlink:`html <td1a_plus_grande_somme2html.html>`, :download:`python <td1a_plus_grande_somme.py>`, :downloadlink:`slides <td1a_plus_grande_somme.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_algo/td1a_plus_grande_somme.ipynb|*`


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 :math:`L=(a_1, ..., a_n)`. On
veut trouver la plus grande liste :math:`l` d’entiers croissante incluse
dans :math:`L`. Cette liste :math:`l` n’est pas nécessairement un bloc
contigü de la liste :math:`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 <http://en.wikipedia.org/wiki/Longest_increasing_subsequence>`__.
L’algorithme le plus rapide est en :math:`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.