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.
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
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 :