Algo

[algo] Tableau et Sous Tableau maximum.

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [algo] Tableau et Sous Tableau maximum.

slvn

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

Publicité

Evadream -jbd-

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

slvn

yep, qui se suivent of course

jahjah

donne un exemple

Evadream -jbd-

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 ?

slvn

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 )

slvn

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

Evadream -jbd-

Pourquoi non ?

slvn

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)

skeye

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

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

Publicité

slvn

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

Evadream -jbd-

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.

@+

slvn

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

Evadream -jbd-

Suis-je bête, bien entendu =)

jagstang

Pa Capona ಠ_ಠ

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

jagstang

Pa Capona ಠ_ಠ

implémentation en java

Code :

public static int maxSubSum3( int [] a )
{
int maxSum = 0;
int thisSum = 0;
for(int j = 0; j< a.length; j++ ) {
thisSum += a[j];
if( thisSum > maxSum )
maxSum = thisSum;
else
if( thisSum < 0 ) {
thisSum = 0; // resets the start index !
}
}
return maxSum;
}

Chronoklazm

On voulait pas un tableau en sortie ?

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

slvn

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

Chronoklazm

Citation :

Sommaire de lalgorithme:

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 !

slvn

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

skeye

slvn a écrit :

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

Code :

<b class="s2">Chronoklaz<span class="s0"> </span>m</b>

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

Chronoklazm

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 !

slvn

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

Chronoklazm

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

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

slvn

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

Publicité

FORUM HardWare.fr

Programmation

Algo

[algo] Tableau et Sous Tableau maximum.

Sujets relatifs
[CSS] Bordure d'un tableau	Algo de recherche de flou
Centrer un tableau en CSS	Probleme de tableau avec des include
Modifier les bordures d'un tableau PHP (débutant inside)	Tableau de HashSet
[algo] algo non recursif pour parcourir les niveaux d'un arbre	[algo] toutes les permutations d'une chaine de charatere
Un pb de caddie avec session php: tableau dans un tableau	Pblm -> Script appelant un tableau
Plus de sujets relatifs à : [algo] Tableau et Sous Tableau maximum.

Page générée en 0.042 secondes