sous-séquence de somme maximale [Résolu]

[jess013]

Bonjour,

Je débute en VBA et j'ai beaucoup de difficulté avec un problème :
Je dois trouver la sous-séquence de somme maximale d'une séquence, avec la position de la première et dernière case de cette sous-séquence.

Pour une séquence de N nombres, je sais que je peux trouver la somme pour chaque début possible en faisant :
pour i = 1 à N
somme = somme + case(i) 'valeur de la ieme case

sans utiliser les valeurs négatives comme début

mais je ne vois pas comment stocker la somme, le début et la fin (dans un tableau?), pour ensuite trouver le max de toutes les sommes

je comprends le problème, mais je ne sais pas par où commencer pour le traduire en VBA

Si quelqu'un pouvait m'aider à partir mon VBA, ce serait très apprécié,

Merci!

[issoram]

Bonjour,

Voici qui fait l'affaire. C'est un algo basique à optimiser suivant tes besoins (non prise en compte des nombres négatifs etc...)

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
30
31
Option Explicit
Option Base 1  'Les indices des tableaux commencent à 1
 
Sub test()
 
    Dim somme_max As Double, somme As Double
    Dim indice_debut, indice_fin As Long  'indices de début et fin de la sous sequence
    Dim sequence() As double
    Dim i As Long, j As Long
 
    sequence = .... 'ici tu initialises ta séquence 
    somme_max = sequence(1) 'On initialise la somme max avec le premier élément
    indice_debut = 1   ' et les indices de même
    indice_fin = 1
 
    For i = 1 To UBound(sequence)
        somme = 0
        For j = i To UBound(sequence)
            somme = somme + sequence(j)
            If (somme > somme_max) Then
                somme_max = somme
                indice_debut = i
                indice_fin = j
            End If
        Next j
 
    Next i
 
Debug.Print (somme_max & " " & indice_debut & " " & indice_fin)
 
End Sub

PS: Attention si ta séquence comportent plusieurs sous_séquences de même somme maximale, une seule sera détectée par cet algo.

Cordialement

[jess013]

Merci pour votre réponse!