Imaginer un Algorithme

Salut,
Voila j’ai envie d’écrire un algorithme pour résoudre le problème suivant:
J’ai une liste de nombres entiers, A0, A2, ... , An-1, dont chacun peut être positifs ou négatifs, trouver la sous-liste de nombres entiers Ai, ..., Aj qui a le montant maximum de toute sous-liste.
Je m’explique : Une sous-liste doit commencer à une certaine position dans la liste originale, jusqu’un à une autre position dans la liste et elle doit comporter tout les nombre qui se suivent dans la liste originale entre ces positions.
Par exemple, si la liste est {10, -20,11, -4,13,3, -5, -17,2,15,1, -7,8}, alors la réponse
est de 23 puisque c'est la plus grande somme qu’on puisse avoir dans cette liste qui est {11, -4,13,3} et aucune autre sous-liste dans la liste n’est plus grande que celle-ci.
Une utilisation possible de cet algorithme est dans l'analyse des marchés boursiers. Supposons que les entiers représentent la hausse ou la baisse des prix de l'action sur une période de temps. Cet algorithme donne la meilleure période de cette action durant son existence.
J’espère que ce n’est pas trop confus.
Cool Raoul

Je ne suis pas sur que ta question soit à la bonne place dans le forum de java (il n'y en a pas un sur les algo ?).

Mais ca ne fait rien ;)

Donc, une solution simple à ton problem serait de faire quelque chose du genre:

Code:

---

1 2 3 4 5 6 7 8

int tmp,max = list[0]; for (int i=0; i<list.length; i++){ for (int j=i ; j < list.length; j++) { tmp = additionElementsTabFromIndex(i,j); if (max < tmp) {max=tmp;} //on peu aussi enregistrer i,j si besoin.. } }

---

Donc l'idée est de faire tous les index de ton tableau (i) pour calculer la somme de chaque sous liste (j) et l'enregistrer si elle est plus grande que le max.
Voila, c'est plus clair ?

Salut Nabodix,
Merci pour ta reponse rapide.
Mais li ya une chose que je n'arrive pas a trouver.
"additionElementsTabFromIndex()" elle appartient a quel package stp.
Merci

C'est normal que tu ne la trouve pas, vu qu'elle n'existe pas; c'était à toi de l'écrire ;)

Je l'ai noté ainsi pour rendre le code compréhensible.. Vu que mon but premier n'était pas d'écrire un code qui marche mais un code qui permetrait de comprendre le truc, afin que tu puisses l'addapter celon tes besoins..


Le but de cette fonction est de calculer la somme des éléments de la sousListe qui va de i à j.
On pourait l'écrire ainsi:

Code:

---

1 2 3 4 5 6 7

public int additionElementsTabFromIndex(i,j){ int toReturn=0; for (int k=i; k<j; k++) toReturn+=list[k]; //"list" est ta liste principale return toReturn; }

---

N'ésite pas à demander si tu ne comprends pas/ ca ne marche toujours pas..

On peut même faire plus simple et plus rapide :

Code:

---

1 2 3 4 5 6 7

for (int i=0; i<list.length; i++){ int tmp = 0; for (int j=i ; j < list.length; j++) { tmp += list[j]; if (max < tmp) {max=tmp;} //on peu aussi enregistrer i,j si besoin.. } }

---

On peut essayer de chercher quelque chose de plus "intelligent".

A partir de la liste de base :
{10, -20, 11, -4, 13, 3, -5, -17, 2, 15, 1, -7, 8}
On construit une liste consolidée :
{10, -20, 11, -4, 16, -22, 18, -7, 8} (on préconstruit les sommes des nombres proches positifs et des nombres proches négatifs)
C'est à partir de cette liste-là qu'on va travailler (on peut retrouver la liste initiale ensuite).

Après, on peut considérer que la liste résultat commencera toujours et finira toujours par un nombre positif (sinon, il suffirait d'enlever le nombre négatif en début/fin pour obtenir un total plus grand).
Donc la liste résultant doit posséder au final un nombre impair d'éléments.

Première opération, on enlève (si besoin est) les nombres négatifs au bord : ils ne servent à rien. Ici, pas de problème, mais si on avait {-2, 4, -30, 5}, on peut enlever le -2 directement.

Ensuite, on peut "simplifier" les bords de la liste de manière récursive : en prenant par bloc de 3 éléments (1 positif, 1 négatif, 1 positif), si le nombre résultant n'est pas supérieur au nombre positif à l'intérieur de la liste, on peut supprimer les deux nombres du bord (le positif au bord et le négatif ensuite).
Ici, on simplifie la liste en : {11, -4, 16, -22, 18, -7, 8}

A partir de là, on peut adopter un algorithme "idiot", mais on a déjà pas mal solutionné.
Attention, pseudo-code à adapter :

Code:

---

1 2 3 4 5 6 7 8

long max = MIN_LONG; for(int i=0; i<length; i+=2) { for(int j=i; j<length; j+=2) { long tmpSum = sum(list, i, j); if(tmpSum > max) max = tmpSum; } }

---

Je pense qu'un niveau perf. et lisibilité, on ne va pas y gagner grand chose par rapport à deux boucles imbriquées (au niveau perf. c'est sûr qu'on va y perdre à cause de la construction de la liste consolidée et des groupements par 3).

Citation:

---

Envoyé par herve91

On peut même faire plus simple et plus rapide :

Code:

---

1 2 3 4 5 6 7 8

for (int i=0; i<list.length; i++){ int tmp = 0; for (int j=i ; j < list.length; j++) { tmp += list[j]; if (max < tmp) {max=tmp;} //on peu aussi enregistrer i,j si besoin.. } }

---

---

Ah oui :D
En effet, c'est bien mieu !


Sinon, bhamp0, j'aime bien ton algo. Je pense bien qu'il pourrait --potentielement-- fournir des performences interressante dans le cas de très grosses listes.

Je suis moins sûr que ca soit le cas pour de moyennes listes..
Surtout qu'avec ta méthode, on ne peut plus extraire la sous-liste "gagnante"..

Citation:

---

Envoyé par nabodix

Sinon, bhamp0, j'aime bien ton algo. Je pense bien qu'il pourrait --potentielement-- fournir des performences interressante dans le cas de très grosses listes.

Je suis moins sûr que ca soit le cas pour de moyennes listes..
Surtout qu'avec ta méthode, on ne peut plus extraire la sous-liste "gagnante"..

---

En effet, comme tout algorithme "travaillé", c'est intéressant pour les cas importants et pas les cas simples.
Par contre, il est tout à fait possible d'extraire la sous-liste gagnante.

Bon bah, après tests, pour des grandes listes, c'est incomparable la différence.
Et pour des petites listes, c'est le même temps ...
(Par contre, je n'ai pas implémenté la récupération de la sous-liste gagnante, mais ça peut se faire.)

Merci a tous, mais je crois que j’ai trouve quelque chose que va plus vite que ce qui j’ai vu jusqu’a présent. Essayer le code suivant:
Parce qu’en faite la méthode doit marcher pour les gros nombres. Supposons que la liste comporte 1000000 de chiffres. Combien de temps ca lui prendra pour faire le travail.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int i=0; int min = 0; int max = 0;   for ( i=0;i<a.length;i++)   if (i>0) a[i] += a[i-1];   if (a[i]-min>=max) max = a[i]-min;   if (a[i]<min) min = a[i];   return max;

---

Désolé mais je vois pas comment ça peut marcher ... en tout cas, je n'obtiens pas le bon résultat avec ton algo.

Essaye ca:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

import java.util.*; class List { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Entrez des chiffres (sur une seule ligne, séparés par des virgules):"); String line = input.nextLine(); String[] numbers = line.split(","); int[] array = new int[numbers.length]; for(int i=0; i<array.length; i++) array[i]=Integer.parseInt(numbers[i].trim()); int highSum = highestSum(array); System.out.println("La somme la plus élevée dd la sous-liste de nombres est: "+highSum); } public static int highestSum(int[] a) { int min = 0; int max = 0; for (int i=0;i<a.length;i++) if (i>0) a[i] += a[i-1]; if (a[i]-min>=max) max = a[i]-min; if (a[i]<min) min = a[i]; return max; } }

---

Ca marche pour les cas simples (et encore, ça ne permet pas d'avoir la sous-liste gagnante, si ?), mais ce n'est pas un algo exact.
Si tu prends la liste suivante en entrée :

Code:

---

10;-20;11;-4;13;3;13;3;13;3;13;3;13;3;-5;-17;2;15;1;2;15;1;2;15;1;2;15;1;-7;8

---

Tu devrais avoir 137 comme résultat, et ton algo donne 138.
(Sous-liste gagnante : [11, -4, 13, 3, 13, 3, 13, 3, 13, 3, 13, 3, -5, -17, 2, 15, 1, 2, 15, 1, 2, 15, 1, 2, 15, 1]).

Salut,
Ca donne 138 parce que c’est le bon résulta.
Si tu add tous les chiffre commençant par 11 a la position 3 j’jusqu’a la fin ca donne 138 et c’est bon parce que -7 avant la fin en le prend on compte puisque on add 8 qui donne une valeur 1 de plus. 137 ce n’est pas le bon résultat parce que on veut la plus grande somme et dans ta liste on peut y avoir 138 qui plus grand. Je pense que tu devrais prender en compte les 2 dernier chiffre.
[11, -4, 13, 3, 13, 3, 13, 3, 13, 3, 13, 3, -5, -17, 2, 15, 1, 2, 15, 1, 2, 15, 1, 2, 15, 1]).==137
[11, -4, 13, 3, 13, 3, 13, 3, 13, 3, 13, 3, -5, -17, 2, 15, 1, 2, 15, 1, 2, 15, 1, 2, 15, 1-7+8]).==138
Alors! d'accord ou pas?

OK, j'avais fait une erreur sur l'algo trivial :)
Par contre, je dois avouer que je ne vois pas comment prouver que l'algo que tu donnes renvoie le bon résultat. Et quid de la sous-liste gagnante ?

La question était :
"J’ai une liste de nombres entiers, A0, A2, ... , An-1, dont chacun peut être positifs ou négatifs, trouver la sous-liste de nombres entiers Ai, ..., Aj qui a le montant maximum de toute sous-liste." On veut le plus grand montant.
Pour le reste essaye de tester, même avec 1000000 000 de nombres j’arrive à avoir un résultat on moine de 2ms

Citation:

---

Envoyé par Cool Raoul

La question était :
"J’ai une liste de nombres entiers, A0, A2, ... , An-1, dont chacun peut être positifs ou négatifs, trouver la sous-liste de nombres entiers Ai, ..., Aj qui a le montant maximum de toute sous-liste." On veut le plus grand montant.

---

Alors pourquoi m'avoir répondu :

Citation:

---

Surtout qu'avec ta méthode, on ne peut plus extraire la sous-liste "gagnante"..

---

Citation:

---

Envoyé par Cool Raoul

Pour le reste essaye de tester, même avec 1000000 000 de nombres j’arrive à avoir un résultat on moine de 2ms

---

Je n'en doute pas, je dis seulement que je ne vois pas comment démontrer que ton algo renvoie toujours le bon résultat. Je n'ai pas dit qu'il n'était pas bon ou pas rapide.

Ok merci pour tout, mais ca m’intéresserai d’avoir l’avis des autres.

Mon avis?
- C'est que je ne te trouve pas très respectueux envers bhamp0, qui a du prendre de son temps pour écrire du code et faire des tests.

- Qu'il me semble, que le but, n'est pas de faire ton travail à ta place, mais de te "débloquer" dans ta recherche. Vu qu'aucun de nous, jusqu'a présent ne connais LA solution idéale (i.e. qui te convient); il faudra faire d'autre tests pour la trouver, et personnellement, je n'aurai pas le temps de les faire.

Pour faire des tests, voici ce que je te conseille:
- Générer beaucoup de listes aléatoire et de lancer les trois algo vu
- Avec les résultats, tu verras si il y en a un qui marche pas, et si tu peux le corriger
- avec la méthode de timeMillis (ou qqch du genre) tu pourras voir le temps d'execution de chacun. Si tu es sur Linux, tu peux aussi lancer ton programme dans un shell avec la fonction time (==> time java TonProgram), pour voir le temps exact d'execution.
- Et tu peux aussi utiliser une méthode de 'runtime' qui te dira quel espace mémoire tu as consommé.

C'est important de le faire avec beaucoup de listes (et de prendre la moyenne des teamps d'execution), sinon tes chiffres ne seront pas fiable..

Si tu as encore des questions, pas de soucis; du moment que ca n'implique pas qu'on bosse à ta place ;)

Je tiens a m’excuse si j’étais irrespectueux envers quiconque, en tout cas ce n’était pas mon intention. J’essayais juste de comprendre et de répondre à ce qui a était dit. Merci a tous.
Cool Raoul