Bonjour,
Je suis en trains de développer une application et pour une partie de ca j'ai besoin de trouver toutes les sous-séquences croissantes d'une séquence des entiers qui sont aux-même maximales .
Je m'explique:
Imaginons la séquences des entiers S={1,5,6,9,2,3,4,7,8}
une sous-séquence croissantes est une sous-séquences de S dont les items sont dans l'ordre croissantes. Une sous-séquence est maximale si elle n'est pas la sous-séquence des autres sous-séquences.
Par ex :
S1={1,5,6,9} ou S2={1,5,6,7,8} sont sous-sequences croissantes et maximales de S. Mais S3={1,5,6,2} n'est pas croissante ou la sous-sequence S4={6,7,8} n'est pas maximale comme il y a une autre sous-sequence S5={1,5,6,7,8} qui contiens S4.
Alors le problématique est de chercher toutes les sous-séquences croissantes et maximales de S.
A dire qu'il y a pleins de travailles sur "LIS" (Longest Increasing Subsequence) (la sous-sequence croissante la plus longue) même des algos avec complexité O(n log n) mais j'ai pas trouvé une solution qui rend toutes les sous-sequences croissantes et maximales de n'importe quelle tille.
Par exemple sur seq S, j'aimrais de trouver les sous-séquences croissantes et maximales ci-dessous :
{1,5,6,9} {1,5,6,7,8} {1,2,3,4,7,8}
je remarque que c'est possible d'avoir plusieurs sous-sequences croissantes maximales exactement de la même taille. donc on s'intéresser d'avoir toutes pas juste une parmi toutes.
Je vous remercie bien de fournir un pesudo code si vous donner un algo pour mieux faire inspirer le structure de données utilisé.
En vous remerciant j'attends vos réponses.