[Python] Plus longue sous-suite croissante

[Charmander]

Bonjour,

Je dois coder en Python un programme qui prend en entrée un tableau u non trié de longueur n et qui me renvoie la plus longue sous-suite croissante. Voici le sujet :

Pour tout i [0, n 1], on note la longueur maximale des sous-suites croissantes de u dont le dernier terme est
a. Programmer une fonction tabLongueurMax(u) qui calcule , ..., de proche en proche (et les renvoie sous forme d’un tableau). En déduire une fonction longueurMax(u) déterminant la longueur maximale des sous-suites croissantes de u.
b. À l’aide des fonctions précédentes, écrire une fonction plssc(u) qui détermine une plus longue sous-suite croissante de u.

J'ai réussi à coder les deux programmes demandés par la question a) , mais je ne sais pas comment les utiliser pour obtenir la plus longue sous-suite croissante... Si vous aviez une idée, pas nécessairement en langage python mais juste l'idée de l'algorithme... merci d'avance !

[fatal_error]

slt,

ben tu sais calculer pour i donné la longueur de la sous suite croissante,
donc t'as mettons n sous suites croissantes dont tu connais leur longueur.
Tu sais que la longueur max c'est M.
T'as juste à chercher parmi tes n sous suites croissantes une qui a pour longueur M.

[Charmander]

slt,

ben tu sais calculer pour i donné la longueur de la sous suite croissante,
donc t'as mettons n sous suites croissantes dont tu connais leur longueur.
Tu sais que la longueur max c'est M.
T'as juste à chercher parmi tes n sous suites croissantes une qui a pour longueur M.

D'accord mais je ne vais pas chercher toutes les suites croissantes pour un n donné, si ? Rien que pour mettons n=5, il y a 5!=120 suites possibles se terminant à n, et je dois tester si elles sont croissantes, puis regarder si elle sont à la longueur maximale, ça en fait beaucoup pour la complexité non?

[LeJeu]

D'accord mais je ne vais pas chercher toutes les suites croissantes pour un n donné, si ? Rien que pour mettons n=5, il y a 5!=120 suites possibles se terminant à n, et je dois tester si elles sont croissantes, puis regarder si elle sont à la longueur maximale, ça en fait beaucoup pour la complexité non?

comme dit Fatal ( que j esalue)

c'est pour ca que l'exo te demande de remplir un tableau intermédiaire de 5 valeurs
qui sont les longueurs des plus grandes suites qui se terminent en 0 en 1 en en .4

ensuite tu n'as plus qu'a chercher le plus grand nb de ces n ( 5) valeurs ca te donne la position du dernier élément de la suite

t'as plus qu'a afficher les max termes de la suite qui se termine à cet endroit