Exercice 8 - Tranche minimale

Etant donné un tableau $T[n]$, un tranche est une suite d'éléments contigüs de $T$. Une tranche $[T_i, \ldots, T_j]$ est entièrement déterminée par l'indice $i$ de début et l'indice $j$ de fin. La valeur de la tranche $[T_i, \ldots, T_j]$ est donnée par la somme

$$V_i^j = \sum_{k = i}^{j}T_k$$

Nous souhaitons mettre au point un algorithme de recherhe de la tranche minimale.

1. Ecrivez un algorithme construit avec trois boucles imbriquées. Calculez sa complexité.
2. Utilisez le fait que $V_i^{j+1} = V_i^{j} + T[j + 1]$ pour écrire un algorithme construit avec deux boucles imbriquées. Calculez sa complexité.
3. Soient $M_i^j$ la valeur de la tranche minimale incluse dans la tranche $[T_i, \ldots, T_j]$, et soit $\hat{M_i^j}$ la tranche minimale de $[T_i, \ldots, T_j]$ contenant $T_j$. Donnez une relation entre $M_i^{j+1}$, $M_i^{j}$ et $\hat{M_i^{j}}$.
4. En déduire un algorithme de recherche de la tranche minimale construit avec une seule boucle. Déterminer sa complexité.