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 trouve une solution qui rend toutes les sous-sequences croissantes et maximales de n'importe quelle tille.
 
je remarque que c'est possible d'avoir plusieurs sous-sequences croissantes maximales de la même taille.
 
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.

à froid ça me semble pas trop chaud, j'ai raté quoi ?
 
tant que la séquence croie, c'est une séquence, dés que ça croie plus, c'est une nouvelle séquence.
 
non ?

On dirait un exo de cours.
Et je vois pas la vraie difficulté, là, en fait.

om nom nom

qu'est-ce tu manges

En fait dans le premier vu ca semble facile mais vous avez pas remarqué que quant il ne croie pas c'est pas forcement une nv sous-seq.  
 
par ex : 1,5,6,7,8 est une sous-seq croissante aussi mais pour y arriver il faut filtrer certains items de seq originale S.  C-a-d quand on arrive à 6 après on peut ajouter 9 et egalement on peut continuer sans ajouter le 9 pour arriver à 7 et l'ajouter.  
 
En plus comme j'ai dit je l'ai fait en O(n²) mais je veut un algo plus rapide.

la vache !!    
 
mais ça veut rien dire !

tu n'est pas obligé d'écrire quand tu sais rien,
cela veut dire des sous-séquences,  mais tu l'as confondu avec sous-string, c'est pour ca que il te semble facile,
 
La définition de sous-séquence et sous-string est assez différent, tu peut le chercher sur WikiPedia.  
 
Alors Les sous-chaînes (sub-string) sont les parties consécutives d'une chaîne (string), alors que les sous-sequences n'ont pas besoin de l'être. cela veut dire que on peut filtrer certains items de séquence originale en respectant l'ordre des items dans la séq originale pour avoir une sous-séquence.
Donc 1,5,6,7,8 est aussi une autre sous-seq de seq S.
 
C'est pour ca que on ne peut pas dire quand il ne croie pas alors on a une nouvelle sous-séquence, non, c'est pas le cas. Parce que c'est possible quand on arrive à une chiffre qui ne croie plus, en le passant on peut avoir un autre chiffre qui croie tjrs. donc on peut filtrer ce qui ne croie pas pour avoir une sous-seq croissante. voila.
 
En plus j'insiste de nv que j'ai développé un algo en O(n²) mais comme il y a un algo de O(n log(log n)) pour trouver seulement la sous-seq croissante la plus longue, donc j'ai pansé peut-etre on peut trouver un algo linaire pour trouver toutes les sous-seqs croissantes et maximales (de n'importe quelle taille).
 
Alors je l'ai expliqué pour les autres mais je croie pas trop que tu (brissou) es la pour une participation sérieux à forum.
 
Merci

ok, au temps pour moi. J'avais pas saisi la subtilité des sous-séquences.

néanmoins, ton problème n'est pas un problème propre à Java, mais plutôt une question d'algorithmique, je te conseillerai donc de modifier la catégorie de ton message (édite ton premier message, et change la catégorie).

edit: sinon, ça a un intérêt dans quel domaine cette recherche de séquence ?

Je l'ai envoyé dans la catégorie de java parce que je panse la performance d'un appli dépend aussi de structure de données utilisé lors d'implementation, alors j'ai pansé peut-etre je peut avoir bonne conseil pour l'implementer sous java.
 
Il y a pleins d'interet pour chercher des sous-sequences croissantes surtout dans le domaine de biologie, bioInformatique  pour savoir quelle pourcentage d'une seq ADN par ex correspond à une autre seq ADN.
 
mais pour moi, je suis en trains de chercher un méthode pour trouver la similarité entre deux motif séquentiel (une sorte particulier de séquence dans le domaine fouille de données) . c'est pour ca je m'intéresse de chercher les sous-seq d'une seq.