Recherche du maximum d’ un ensemble de valeurs

Dans un tableau A on cherche à déterminer la plus grande valeur. Pour cela on peut décider de conserver l’indice de la valeur maximale dans un variable qu’on apellera max et parcourir le tableau, chaque fois que A[max] sera plus petit que la valeur courante du tableau on fera passer max à la valeur courante de i.

On passe par la ligne si A[i] > A[max] alors autant de fois qu’ il y a d’éléments du tableau - 1 ;

Recherche de segments maximaux O(n³)

Un tableau A contient des nombres positifs et négatifs. En fait ce sont les coefficients d’hydrophobicité des acides aminés consécutifs d’une protéine transmembranaire. En voici quatre exemples, pour vos essais :

Dans ce tableau A on cherche à determiner quels sont les positions i et j telles que la somme A[i] + A[i+1] + ... +A[j] est la plus grande possible. La séquence des acides aminés de rang i à j correspond probablement à une partie de la protéine qui est dans la membrane.

Allons y lentement.

On peut imaginer partir de chaque valeur possible de i et calculer toutes les sommes pour toutes les cases successives, chaque fois qu’on a une valeur plus élevée que la plus haute obtenue pour l’instant on met à jour des variables imax et jmax.

combien de fois faisons nous V ← v + A[k] ?

combien de fois faisons nous si V > Vmax alors ?

combien de fois faisons nous V ← 0 ?

Le programme O(n³)

Aller plus vite ? O(n²)

On peut aussi commencer par sommer les cases successives du tableau que l’on enregistrera dans un tableau annexe B de la sorte dans la case de rang i+1 de B on aura la somme de valeurs des cases A[0], A[1], A[2], ... jusqu’à A[i]. La valeur B[0] est donc nécessairement 0. Dans ce cas la valeur de B[j+1] - b[i] est la valeur de la somme des cases A[i] + a[i+1] + ... + a[j]. On voit qu’il est alors possible d’éliminer la boucle interne de l’algorithme Segments maximaux 1.

On obtient l’algorithme :

Le programme O(n²)

Aller plus vite ? O(n¹)

Considérons le tableau B de la section précédente. Le segment maximal est celui dont les cases extrêmes sont i et j tel que pour lesquels B[j+1] - B[i] est maximal ! En quelque sorte si nous considérons le graphe de la fonction décrite par B, ce qui nous intéresse c’est le plus grand dénivelé entre une valeur de B[j+1] et B[i].

Si lorsque nous examinons successivement toutes les valeurs de B, et que au moment où nous examinons B[j+1] nous sachions quel est le imax tel que B[imax] est la plus petite valeur de B observée entre les cases 0 et j de B alors il est clair que B[j+1] -B[imax] est la valeur du segment de A dont les sommes des valeurs se terminant en A[j] est la plus élevée.

Décidons donc de créer un tableau C de même longueur que B et tel qu’en C[k] on trouve la position imax telle que B[imax] est la plus petite valeur de B entre les cases 0 et k. Dans ce cas on sait que B[j+1] -B[C[j]] est la valeur du segment maximal se terminant en A[j], il commence en C[j]. Le segment maximal de A est donc celui compris entre C[j] et j tel que B[j+1] -B[C[j]] est maximal. L’algorithme devient donc calculer B, calculer C, calculer D qui contient en j les valeurs de B[j+1] -B[C[j]], trouver la valeur la position de la valeur maximale de D, c’est la position de fin du segment maximal, à cette position en C on trouve la position de début du segment et en D a cette position la valeur du segment. L’algorithme s’écrit :

Le programme O(n¹)

Exercice : a-t-on besoin de tous ces tableaux ?

Que fait :