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

Le problème maximal des sous-arraies est le même que le problème de tranche maximale. Ce tutoriel discute du problème avec le 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 tout le tableau. Ce problème et sa solution dans n'importe quelle langue sont appelés le problème maximal de la sous-table. Le tableau peut avoir des nombres négatifs possibles.

La solution doit être efficace. Il doit avoir la complexité la plus rapide. À partir de maintenant, l'algorithme le plus rapide de 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érez le vecteur suivant (tableau):

vecteur A = 5, -7, 3, 5, -2, 4, -1;

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 l'ensemble du tableau, ne donnera une somme jusqu'à la valeur de 10. L'ensemble du tableau donne une somme de 7, ce qui n'est pas la somme maximale.

Considérez le vecteur suivant:

vecteur B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

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 au sein de la sous-table.

Considérez le vecteur suivant:

vecteur C = 3, 2, -6, 4, 0;

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

Considérez le vecteur suivant:

vecteur D = 3, 2, 6, -1, 4, 5, -1, 2;

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 tout le tableau.

Considérez le vecteur suivant:

vecteur E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Il y a deux sous-terrains avec des sommes maximales, ici. La somme la plus élevée est celle qui est considérée comme une solution (réponse) pour le problème maximal de sous-tableaux. Les sous-arrayons 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érez le vecteur suivant:

vecteur F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Il y a deux sous-terrains avec des sommes maximales. La somme la plus élevée est celle qui est considérée comme une solution pour le problème maximal de la sous-table. Les sous-terrains 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 rechercher le sous-tableau avec la somme la plus élevée et non le sous-tableau avec la somme supérieure.

Développer l'algorithme de Kadane

Les informations dans cette section du tutoriel ne sont pas l'œuvre originale de Kadane. C'est la manière de l'auteur pour enseigner l'algorithme de Kadane. L'un des vecteurs ci-dessus, avec ses totaux de course, se trouve dans ce tableau:

Exécuter le total pour un index est la somme de toutes les valeurs précédentes, y compris celle pour l'index. Il y a deux séquences avec des sommes maximales ici. Ils sont 5, 7, qui donne une somme de 12, et 6, 5, 10, -5, 15, 4, qui donne une somme de 35. La séquence qui donne une somme de 35 est ce qui est souhaité.

Notez que pour les totaux de course, 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 de course tout en comparant les sommes maximales lorsqu'ils sont rencontrés, se déplaçant de gauche à droite dans le tableau donné.

Un autre vecteur d'en haut, avec ses totaux de course, 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 souhaité.

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

Encore une fois, l'idée de l'algorithme de Kadane est de faire le total de course tout en comparant les sommes maximales lorsqu'ils sont rencontrés, 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 ce que Kadane a utilisé. Cependant, c'est par son algorithme. Le programme comme de nombreux autres programmes C ++ commencerait:

#inclure
#inclure

Utilisation de Namespace 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 de fonctionnement tout en comparant les sommes maximales lorsqu'ils sont rencontrés, se déplaçant de gauche à droite dans le tableau donné. La fonction de l'algorithme est:

int maxsunarray (vecteur &UN)
int n = a.taille();
int maxsum = a [0];
int runtotal = a [0];
pour (int i = 1; i < N; i++)
int tempuntotal = runtotal + a [i]; // pourrait être plus petit qu'un [i]
if (a [i]> tempuntotal)
runTotal = a [i]; // Au cas où un [i] est plus grand que l'exécution totale
autre
RunTotal = tempruntotal;
if (runTotal> maxsum) // comparant toutes les sommes maximales
maxsum = runTotal;

retourner maxsum;

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 en cours d'exécution à chaque index. Ils sont tous deux initialisés avec la première valeur du tableau. Dans cet algorithme, si la valeur suivante du tableau est supérieure au total en cours d'exécution, cette valeur suivante deviendra le nouveau total de course.

Il y a une boucle principale. La numérisation commence à partir de 1 et non zéro en raison de l'initialisation des variables, maxsum et runtotal à un [0] que le premier élément du tableau donné.

Dans la boucle for, la première instruction détermine un total d'exécution temporaire en ajoutant la valeur actuelle à la somme accumulé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 en cours d'exécution jusqu'à présent, alors cette valeur unique devient le total en cours d'exécution. Ceci est pratique surtout si toutes les valeurs du tableau donné sont négatives. Dans ce cas, la valeur négative la plus élevée seule deviendra la valeur maximale (la réponse). Si la valeur actuelle à elle seule n'est pas supérieure au total d'exécution temporaire jusqu'à présent, alors le total de course devient le total de course 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-Loop 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-tableaux. Notez que le total de fonctionnement augmenterait et augmenterait, car le tableau est scanné de gauche à droite. Il tombe en répondant aux valeurs négatives.

La somme maximale de sous-argent finale choisie est retournée après la boucle pour.

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

vecteur A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxsunArray (a);
couter << ret1 << endl;
vecteur B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, −1, 2, 1 -> 6
int ret2 = maxsunArray (b);
couter << ret2 << endl;
vecteur C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxsunArray (c);
couter << ret3 << endl;
vecteur D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxsunArray (d);
couter << ret4 << endl;
vecteur E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxsunArray (e);
couter << ret5 << endl;
vecteur F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2; // 10, 15, 9 -> 34
int ret6 = maxsunArray (f);
couter << ret6 << endl;

Avec cela, la sortie sera:

dix

6

5

20

35

34

Chaque réponse de ligne 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é de temps est la plus rapide pour le problème maximal de sous-traits. Il existe d'autres algorithmes qui sont plus lents. L'idée de l'algorithme de Kadane est de faire le total de fonctionnement, tout en comparant les sommes maximales telles qu'elles sont rencontrées, se déplaçant de gauche à droite dans le tableau donné. Si la valeur actuelle seule est supérieure au total en cours d'exécution jusqu'à présent, alors cette valeur unique devient le nouveau total en cours d'exécution. Sinon, le nouveau total de course est le total de course précédent plus l'élément actuel, comme prévu, car le tableau donné est numérisé.

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

Quels sont les index limitants pour la plage de la somme maximale choisie? - C'est une discussion pour une autre fois!

Chrys