Sous-tableau de produit maximum

• Le produit maximum est $48=2\times (-3)\times (-2)\times 4$. Les suffixes non vides de $[2,-3]$ ont pour produits $-3$ et $-6$ : le meilleur est $[-3]$. Prolongé par $-2$, il donne $6$, alors que le pire suffixe, $[2,-3]$, donne $12$. Un suffixe de produit très négatif devient le meilleur dès qu'on le multiplie par un nombre négatif : connaître le seul meilleur suffixe ne suffit plus pour la progression.

nom : T
valeurs : 2 -3 -2 4 -1 0 5
vert : 0..3
zone : 0..3 produit 48
legende : le produit maximum : 2 × (-3) × (-2) × 4 = 48

nom : T
valeurs : 2 -3 -2 4 -1 0 5
griser : 2..6
pointeurs : k=2
zone : 0..1 pire : -6
zone : 1..1 meilleur : -3
legende : prolongés par -2 : le meilleur suffixe donne 6, le pire 12

• Invariant $I(p_m,s_{\max },s_{\min },k)$ : « $p_m$ est le produit maximum d'un sous-tableau non vide du $k$-préfixe ; $s_{\max }$ et $s_{\min }$ sont les produits maximum et minimum d'un suffixe non vide du $k$-préfixe ». Un suffixe non vide du $(k+1)$-préfixe est $T[k:k+1]$ seul, ou un suffixe non vide du $k$-préfixe prolongé par $T[k]$. Le produit par $x=T[k]$ étant monotone (croissant si $x\ge 0$, décroissant sinon), les extrêmes sont atteints en $s_{\max }$ ou en $s_{\min }$ :

$$s_{\max }^{\prime }=\max (x,s_{\max }x,s_{\min }x),s_{\min }^{\prime }=\min (x,s_{\max }x,s_{\min }x),p_m^{\prime }=\max (p_m,s_{\max }^{\prime }).$$

Initialisation : $I(T[0],T[0],T[0],1)$. -

static long produitMax(int[] T) { int n = T.length;   // n ≥ 1
    long smax = T[0], smin = T[0], pm = T[0]; int k = 1;  // I(T[0],T[0],T[0],1)
    while (k != n) {                  // I(pm,smax,smin,k) et k ≠ n
        long x = T[k], a = smax * x, b = smin * x;
        smax = Math.max(x, Math.max(a, b)); // meilleur suffixe non vide
        smin = Math.min(x, Math.min(a, b)); // pire suffixe non vide
        k = k + 1;
        if (smax > pm) pm = smax;     // I(pm,smax,smin,k)
    }                                 // I(pm,smax,smin,n)
    return pm;
}

$\Theta (n)$. Le programme Exercices11.java la compare à la version naïve sur $20000$ tableaux aléatoires :

[2, -3, -2, 4, -1, 0, 5] : 48 (naif 48)
[-2, 3, -4] : 24 (naif 24)
[-1] : -1 (naif -1)
[0, -2, 0] : 0 (naif 0)
[2, 3, -2, 4] : 6 (naif 6)
20000 tableaux aleatoires : identiques