Problème de sous-tableau maximum en C++

Le problème de sous-tableau maximum est le même que le problème de tranche maximum. Ce didacticiel traite du problème de codage en C++. La question est : quelle est la somme maximale de toute séquence possible de nombres consécutifs dans un tableau ? Cela peut signifier l'ensemble du tableau. Ce problème et sa solution dans n'importe quel langage, est appelé le problème de sous-tableau maximum. Le tableau peut avoir des nombres négatifs possibles.

La solution doit être efficace. Il doit avoir la complexité temporelle la plus rapide. À l'heure actuelle, l'algorithme le plus rapide pour la solution est connu dans la communauté scientifique sous le nom d'algorithme de Kadane. Cet article explique l'algorithme de Kadane avec C++.

Exemples de données

Considérons le vecteur (tableau) suivant :

La tranche (sous-tableau) avec la somme maximale est la séquence, {3, 5, -2, 4}, qui donne une somme de 10. Aucune autre séquence possible, même la totalité du tableau, ne donnera une somme allant jusqu'à la valeur de 10. L'ensemble du tableau donne une somme de 7, qui n'est pas la somme maximale.

Considérons le vecteur suivant :

La tranche (sous-tableau) avec la somme maximale est la séquence, {4, -1, 2, 1} qui donne une somme de 6. Notez qu'il peut y avoir des nombres négatifs dans le sous-tableau pour la somme maximale.

Considérons le vecteur suivant :

La tranche (sous-tableau) avec la somme maximale est la séquence, {3, 2} qui donne une somme de 5.

Considérons le vecteur suivant :

Le sous-tableau avec la somme maximale est la séquence, {3, 2, 6, -1, 4, 5, -1, 2} qui donne une somme de 20. C'est le tableau entier.

Considérons le vecteur suivant :

Il y a deux sous-tableaux avec des sommes maximales, ici. La somme la plus élevée est celle qui est considérée comme solution (réponse) pour le problème du sous-tableau maximum. Les sous-tableaux sont : {5, 7} avec une somme de 12, et {6, 5, 10, -5, 15, 4} avec une somme de 35. Bien sûr, la tranche avec la somme de 35, est la réponse.

Considérons le vecteur suivant :

Il existe deux sous-tableaux avec des sommes maximales. La somme la plus élevée est celle qui est considérée comme solution pour le problème du sous-réseau maximum. Les sous-tableaux sont : {10, 15, 9} avec une somme de 34, et {4, 6, 3, 2, 8, 3} avec une somme de 26. Bien sûr, la tranche avec la somme de 34 est la réponse car le problème est de chercher le sous-tableau avec la somme la plus élevée et non le sous-tableau avec la somme la plus élevée.

Développement de l'algorithme de Kadane

Les informations contenues dans cette section du didacticiel ne sont pas le travail original de Kadane. C'est la propre manière de l'auteur d'enseigner l'algorithme de Kadane. L'un des vecteurs ci-dessus, avec ses totaux cumulés, se trouve dans ce tableau :

Le total cumulé d'un index est la somme de toutes les valeurs précédentes, y compris celle de l'index. Il y a deux séquences avec des sommes maximales ici. Ce sont {5, 7}, ce qui donne une somme de 12, et {6, 5, 10, -5, 15, 4}, ce qui donne une somme de 35. La séquence qui donne une somme de 35 est celle que l'on souhaite .

Notez que pour les totaux cumulés, il y a deux pics qui sont les valeurs 12 et 27. Ces pics correspondent aux derniers index des deux séquences.

Ainsi, l'idée de l'algorithme de Kadane est de faire le total cumulé tout en comparant les sommes maximales au fur et à mesure qu'elles sont rencontrées, en se déplaçant de gauche à droite dans le tableau donné.

Un autre vecteur ci-dessus, avec ses totaux cumulés, se trouve dans ce tableau :

Il y a deux séquences avec des sommes maximales. Ce sont {10, 15, 9}, ce qui donne une somme de 34 ; et {4, 6, 3, 2, 8, 3} qui donne une somme de 26. La séquence qui donne la somme de 34, est ce qui est désiré.

Notez que pour les totaux cumulés, il y a deux pics qui sont les valeurs, 30 et 13. Ces pics correspondent aux derniers indices des deux séquences.

Encore une fois, l'idée de l'algorithme de Kadane est de faire le total cumulé tout en comparant les sommes maximales au fur et à mesure qu'elles sont rencontrées, en se déplaçant de gauche à droite dans le tableau donné.

Code par l'algorithme de Kadane en C++

Le code donné dans cette section de l'article n'est pas nécessairement celui utilisé par Kadane. Cependant, c'est par son algorithme. Le programme, comme beaucoup d'autres programmes C++, commencerait par :

en utilisant l'espace de noms std ;

Il y a l'inclusion de la bibliothèque iostream, qui est responsable de l'entrée et de la sortie. L'espace de noms standard est utilisé.

L'idée de l'algorithme de Kadane est d'avoir le total cumulé tout en comparant les sommes maximales au fur et à mesure qu'elles sont rencontrées, en se déplaçant de gauche à droite dans le tableau donné. La fonction de l'algorithme est :

La taille, N du tableau donné (vecteur) est déterminée. La variable, maxSum est l'une des sommes maximales possibles. Un tableau a au moins une somme maximale. La variable, runTotal représente le total cumulé à chaque index. Ils sont tous deux initialisés avec la première valeur du tableau. Dans cet algorithme, si la valeur suivante dans le tableau est supérieure au total cumulé, cette valeur suivante deviendra le nouveau total cumulé.

Il existe une boucle for principale. Le balayage commence à partir de 1 et non de zéro en raison de l'initialisation des variables, maxSum et runTotal à A[0] qui est le premier élément du tableau donné.

Dans la boucle for, la première instruction détermine un total cumulé temporaire en ajoutant la valeur actuelle à la somme cumulée de toutes les valeurs précédentes.

Ensuite, il y a une construction if/else. Si la valeur actuelle seule est supérieure au total cumulé jusqu'à présent, cette valeur unique devient le total cumulé. C'est pratique surtout si toutes les valeurs du tableau donné sont négatives. Dans ce cas, seule la valeur négative la plus élevée deviendra la valeur maximale (la réponse). Si la valeur actuelle seule n'est pas supérieure au total cumulé temporaire jusqu'à présent, alors le total cumulé devient le total cumulé précédent plus la valeur actuelle, - c'est la partie else de la construction if/else.

Le dernier segment de code de la boucle for choisit entre toute somme maximale précédente pour une séquence précédente (sous-tableau) et toute somme maximale actuelle pour une séquence actuelle. La valeur la plus élevée est donc choisie. Il peut y avoir plus d'une somme maximale de sous-matrices. Notez que le total cumulé augmenterait et diminuerait, car le tableau est balayé de gauche à droite. Il tombe lorsqu'il rencontre des valeurs négatives.

La somme finale maximale du sous-tableau choisi est renvoyée après la boucle for.

Le contenu d'une fonction principale C++ appropriée, pour la fonction d'algorithme de Kadane est :

Avec cela, la sortie sera:

dix

6

5

vingt

35

3. 4

Chaque ligne répond ici, correspond à un tableau donné, dans l'ordre.

Conclusion

La complexité temporelle de l'algorithme de Kadane est O(n), où n est le nombre d'éléments dans le tableau donné. Cette complexité temporelle est la plus rapide pour le problème de sous-réseau maximum. Il existe d'autres algorithmes plus lents. L'idée de l'algorithme de Kadane est de faire le total cumulé, tout en comparant les sommes maximales au fur et à mesure qu'elles sont rencontrées, en se déplaçant de gauche à droite dans le tableau donné. Si la valeur actuelle seule est supérieure au total cumulé jusqu'à présent, cette valeur unique devient le nouveau total cumulé. Sinon, le nouveau total cumulé est le total cumulé précédent plus l'élément actuel, comme prévu, lors de l'analyse du tableau donné.

Il peut y avoir plus d'une somme maximale, pour différents sous-réseaux possibles. La somme maximale la plus élevée, pour tous les sous-réseaux possibles, est choisie.

Quels sont les indices limites de la plage de la somme maximale choisie ? – C'est une discussion pour une autre fois !

Chrys