Sous-suite croissante

Dans cet exercice, vous devez extraire une sous-suite d'une suite donnée. La sous-suite extraite doit être croissante (pas forcément strictement) et doit être de longueur maximale.

Par exemple, si la suite donnée en entrée est :

        (3 ,1 , 12 , 2, 7, -6, 11)

Alors, la seule réponse possible est 1,2,7,11.

La sous-suite extraite 1,7,-6, par exemple, n'est pas croissante. La sous-suite extraite 3,7,11 est bien croissante, mais elle n'est pas de longueur maximum.

Le coin tuto

Idée pour résoudre le problème

L'idée générale est la suivante. En partant de la dernière valeur de la suite s[], chercher la plus longue sous suite qui démarre par cette valeur.

Pour un indice de départ dans la liste (i), la plus longue sous suite issue de i a pour longueur : 1 + ( la longueur de la plus longue sous suite parmi les sous suites issues de j où j>i, et s[j]>=s[i])