Sous-tableau de somme maximum : les indices

Chaque appel retourne un triplet $\{s,p,q\}$. Les deux boucles du cas « à cheval » mémorisent, en plus de la meilleure somme, l'indice où elle est atteinte.

static int[] ssm(int[] T, int i, int j) {              // {s, p, q}
    if (j - i == 0) return new int[] {0, i, i};         // sous-tableau vide
    if (j - i == 1) return T[i] > 0 ? new int[] {T[i], i, j} : new int[] {0, i, i};
    int k = (i + j) / 2;
    int[] g = ssm(T, i, k), d = ssm(T, k, j);
    int s = 0, sg = 0, p = k;                           // meilleur suffixe T[p:k]
    for (int a = k - 1; a >= i; a--) { s += T[a]; if (s > sg) { sg = s; p = a; } }
    s = 0; int sd = 0, q = k;                           // meilleur préfixe T[k:q]
    for (int b = k; b < j; b++) { s += T[b]; if (s > sd) { sd = s; q = b + 1; } }
    int[] best = g[0] >= d[0] ? g : d;
    return (sg + sd > best[0]) ? new int[] {sg + sd, p, q} : best;
}

13.5 : ssm = 6, T[2:6] = [4, -1, 2, 1]
13.5 : tout negatif : ssm = 0, T[0:0]

nom : T
valeurs : 2 -3 4 -1 2 1 -5 3
vert : 2..5
pointeurs : p=2 k=4 q=6
zone : 2..3 suffixe 3
zone : 4..5 préfixe 3
legende : à cheval sur k = 4 : 3 + 3 = 6 bat les deux moitiés (4 et 3)

Si toutes les valeurs sont négatives, le meilleur sous-tableau est le sous-tableau vide, de somme $0$ (convention du cours). La complexité reste $\Theta (n\log n)$.