Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Sous-sequence croissante

Posté par
Yamato
29-12-10 à 23:36

Bonjour.

J'ai un probleme pour ceux qui s'y connaissent en algo ^^.


J'ai une sequence de N entiers, je dois trouver une sous-sequence maximale (pas forcement contigue) strictement croissante, c'est a dire une sous-sequence strictement croissante qui comporte le plus d'elements possible.

Exemple :
Sequence : 9 13 17 11 5 13 12 15.
Sous-sequence maximale : 9 11 13 15.
Une autre possible : 9 11 12 15.


Personnellement j'ai trouver un algo qui marche en O(n^2), mais il en faudrait un en O(log n). Quelqu'un a des idees?

Merci.

Posté par
ericdk
Sous-sequence croissante 02-04-11 à 11:57

Bonjour,

je ne propose pas une résolution mais une piste à creuser:
en considérant le rang de chacun de ces entiers, on peut représenter sur un graphe
les points de coordonnées:
(1;9) ((2;13) (3;17) (4;11) (5;5) (6;13) (7;12) (8;15)
soit A le point (1;9) et B (8;15)
on trace la droite (AB). Ensuite en cherchant les points les moins éloignés de cette droite
avec quelques tests bien choisis....
(bien sur, on peut éliminer au départ les points dont la valeur n'est pas comprise entre 9 et 15.

en espérant t'avoir aidé.
Eric

Posté par
Bachstelze
re : Sous-sequence croissante 02-04-11 à 15:29

Bonjour

le problème de la sous-suite croissante (le terme anglais sequence se traduit par suite en français) n'est certainement pas soluble en O(log n), il n'y aurait même pas le temps de passer en revue tous les éléments. Il est par contre soluble en O(nlog n).

Posté par
Yamato
re : Sous-sequence croissante 03-04-11 à 15:11

Bonjour,

Ben dis donc je croyais que ce sujet était tombé dans l'oubli...merci d'avoir répondu en tout cas. En fait j'ai déjà trouvé la solution depuis le temps.

ericdk > Je ne pense pas qu'un algorithme géométrique puisse marcher ici, puisqu'il s'agit en fait d'un algo dynamique.

Bachstelze > Oui, c'était une faute de frappe...je voulais dire O(nlog n)...c'est sûr que ça aurait été trop beau en O(log n). J'ai regardé ton lien, c'est à peu près ce que j'avais trouvé.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !