Sous-séquence croissante de somme maximum — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Sous-séquence croissante de somme maximum

Graphes sans circuit et ordonnancement de projets · niveau 2

Énoncé

Parmi les sous-séquences croissantes de $S$ , on cherche une sous-séquence de somme maximum (et non plus de longueur maximum).

On note $p (j)$ la somme maximum d'une sous-séquence croissante finissant à l'indice $j$ . Donner la récurrence.
Écrire le programme, et l'exécuter sur la séquence $S$ de l'exercice 7.11 puis sur $T = [1, 101, 2, 3, 100, 4, 5]$ .
Sur $T$ , la sous-séquence de somme maximum est-elle une plus longue sous-séquence croissante ?

Corrigé

Avec $pred (j) = {i < j : s_{i} < s_{j}}$ (les valeurs sont positives ou nulles) : base, $p (j) = s_{j}$ si $pred (j) = \emptyset$ ; hérédité, $p (j) = s_{j} + max_{i \in pred (j)} p (i)$ sinon.
On remplace « longueur $+ 1$ » par « somme $+ s_{j}$ » :


static int[][] calculerPA(int[] S) { int n = S.length;
    int[] P = new int[n], A = new int[n];
    for (int j = 0; j < n; j++) {
        P[j] = S[j]; A[j] = -1;                  // base : S[j] seul
        for (int i = 0; i < j; i++)
            if (S[i] < S[j] && P[i] + S[j] > P[j]) { P[j] = P[i] + S[j]; A[j] = i; }
    }
    return new int[][] {P, A};
}


P = [6, 5, 1, 3, 6, 10, 15, 3, 22, 21, 30, 0, 1]
somme max = 30 : 1 2 3 4 5 7 8
T : longueur 5, somme max = 106 : 1 2 3 100


nom : S
valeurs : 6 5 1 2 3 4 5 2 7 6 8 0 1
vert : 2..6 8 10
fleches : 2->3 3->4 4->5 5->6 6->8 8->10
legende : somme maximum 1 + 2 + 3 + 4 + 5 + 7 + 8 = 30 ; flèches de a(j) vers j

Non : sur $T$ , la plssc $1, 2, 3, 4, 5$ a pour longueur $5$ et pour somme $15$ , alors que $1, 2, 3, 100$ (longueur $4$ ) a pour somme $106$ . Les deux critères donnent des solutions différentes.


nom : T
valeurs : 1 101 2 3 100 4 5
vert : 0 2 3 5 6
legende : plus longue, somme 15


nom : T
valeurs : 1 101 2 3 100 4 5
vert : 0 2 3 4
legende : somme maximum : 106