[algo] Tableau et Sous Tableau maximum.

Tableau et Sous Tableau maximum. [algo] - Algo - Programmation

Marsh Posté le 15-03-2005 à 00:28:20    

Hello,
 
Soit un Tableau de N entier signés, donc positifs et négatifs.
Comment trouver le sous-tableau donc la somme des éléments est maximales :)
 
/sylvain

Reply

Marsh Posté le 15-03-2005 à 00:28:20   

Reply

Marsh Posté le 15-03-2005 à 01:29:25    

Tu sépares les nombres positifs des nombres négatifs ?
Si il n'y a que des négatifs, tu prends le maximum, si il n'y que des positifs ou bien des positifs et des négatifs, tu ne prends que les positifs ?
 
[:ddr555], j'ai pas du comprendre qqchose. Par sous tableau, tu entends quoi ? Des éléments qui se suivent ?
 
@+


Message édité par Evadream -jbd- le 15-03-2005 à 01:31:10
Reply

Marsh Posté le 15-03-2005 à 01:37:11    

yep, qui se suivent :D of course :)

Reply

Marsh Posté le 15-03-2005 à 01:44:58    

donne un exemple

Reply

Marsh Posté le 15-03-2005 à 01:49:54    

Tu peux extraire tous les nombres positifs qui se suivent déja. Ca te fait une liste, et tu les compares :
 
1 2 3 4 -5 -2 4 8 4 2 -2 1 5 2
 
Tu obtiens comme sous tableaux :
1 2 3 4 (10) | 4 8 4 2 (18) | 1 5 2 (8)
 
Sous tableau max : 4 8 4 2
 
C'est ca que tu veux ?
 

Reply

Marsh Posté le 15-03-2005 à 01:55:59    

un exemple :
[0 0 0 0 0 -1 -1 -1 1 1 -1 -1 -1 -1 0]
il faut extraire [1 1]
 
le truc ca serait d'extraire le "sous-tableau" dont la somme des elements est la plus grande :)
 
(je dis pas que c'est facile mais ca l'air marrange a faire :D)

Reply

Marsh Posté le 15-03-2005 à 01:56:54    

Evadream -> yep je crois que ton exemple n'est pas ok

Reply

Marsh Posté le 15-03-2005 à 10:30:05    

Pourquoi non ?

Reply

Marsh Posté le 15-03-2005 à 12:09:20    

bah on peut etre extraire un tableau different, dont la somme des elemetns est plus grande. (en fait le tableau max, c'est tt le tableau je crois)

Reply

Marsh Posté le 15-03-2005 à 12:13:10    

Ca ressemble quand même vachement à un exo...[:itm]


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 15-03-2005 à 12:13:10   

Reply

Marsh Posté le 15-03-2005 à 12:42:48    

ouais c'est vrai ca ressemble ;) mais ce n'en n'est pas un..
(enfin je veux dire que personne n'est ici en train de faire mes devoirs)
 
 
Au fait, j'ai deja des elements de reponses.
 
Tout le monde a vu l'algo en O(n3) quand meme :)

Reply

Marsh Posté le 15-03-2005 à 12:48:13    

slvn a écrit :

bah on peut etre extraire un tableau different, dont la somme des elemetns est plus grande. (en fait le tableau max, c'est tt le tableau je crois)


 
Tu crois ? :)
Je dois pas comprendre ton probleme. Montre moi en quoi mon exemple esrt incorrecte. Je ne vois pas comment extraire un sous tableau dont la somme des élements est plus grande.
 
@+

Reply

Marsh Posté le 15-03-2005 à 12:54:35    

Le tableau est 1 2 3 4 -5 -2 4 8 4 2 -2 1 5 2
 
tu dis que le sous tableau max est 4 8 4 2, hors sa somme vaut "18".
Si j'extrais 4 8 4 2 -2 1 5 2, la somme vaut 24, donc ton tableau n'etait pas maximal.  
 
D'ailleurs le mien non plus,  
ici le tableau max est le tableau lui meme:  1 2 3 4 -5 -2 4 8 4 2 -2 1 5 2


Message édité par slvn le 15-03-2005 à 12:55:07
Reply

Marsh Posté le 15-03-2005 à 13:56:01    

Suis-je bête, bien entendu =)

Reply

Marsh Posté le 15-03-2005 à 14:14:48    

il y a un algo en O(n) pour ça.
 
il ne faut tester que des suites de nombres qui ne commencent PAS par une suite de somme négative

Reply

Marsh Posté le 15-03-2005 à 14:25:49    

implémentation en java
 

Code :
  1. public static int maxSubSum3( int [] a )
  2.   {
  3.   int maxSum = 0;
  4.   int thisSum = 0;
  6.   for(int j = 0; j< a.length; j++ ) {
  7.     thisSum += a[j];
  8.     if( thisSum > maxSum )
  9.          maxSum = thisSum;
  10.      else
  11.        if( thisSum < 0 ) {
  12.            thisSum = 0; // resets the start index !
  13.       }
  14.    }
  15. return maxSum;
  16. }

Reply

Marsh Posté le 15-03-2005 à 18:13:30    

On voulait pas un tableau en sortie ? :)


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 18:31:52    

non non pas forcement le tableau en sortie, par contre si on a la position du premier et dernier element ca peut le faire :)
 
Y a bien un algo en O(n) je crois :)
mais l'algo est incomplet :/


Message édité par slvn le 15-03-2005 à 18:46:38
Reply

Marsh Posté le 15-03-2005 à 18:36:00    

Citation :


      Sommaire de l’algorithme:
 
      Déterminer récursivement la sous-séquence de somme maximale uniquement dans la première moitié.  
 
      Déterminer récursivement la sous-séquence de somme maximale uniquement dans la deuxième moitié.  
 
      Avec deux boucles consécutives, déterminer la sous-séquence de somme maximale qui débute dans la première moitié et qui termine dans la deuxième moitié.  
 
      Choisir la somme la plus élevée des trois.


Message édité par Chronoklazm le 15-03-2005 à 18:36:18

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 18:44:37    

question qui a rien a voir :D
Chronoklazm >>p koi quand fait un copy paste de ton nom, il me rajoute un espace: ex "Chronoklaz m"

Reply

Marsh Posté le 15-03-2005 à 18:45:36    

slvn a écrit :

question qui a rien a voir :D
Chronoklazm >>p koi quand fait un copy paste de ton nom, il me rajoute un espace: ex "Chronoklaz m"


Code :
  1. <b class="s2">Chronoklaz<span class="s0"> </span>m</b>


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 15-03-2005 à 18:47:02    

Les dieux du forum n'aiment pas ce mot peut etre :)


Message édité par Chronoklazm le 15-03-2005 à 18:47:27

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 18:49:07    

Mais qu'est ce qu'il fout la ce "span"

Reply

Marsh Posté le 15-03-2005 à 20:29:37    

Hum hum ... et la k-ieme plus longue sous-sequence ?  :hello:  


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 15-03-2005 à 20:36:20    

héhé, interessant ca!
ca impose de changer d'algo, car celui JagStang ignore les sommes négatives. La k'eme sequence pouvant etre négative :/

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed