Discussion :

[Cool Raoul]

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

[nabodix]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[Cool Raoul]

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

[nabodix]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[herve91]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[bhamp0]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
   }
}

[nabodix]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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