Algorithme de Kadence : sous-réseau contigu à la plus grande somme

Quelle est la plus grande somme des sous-tableaux contigus ?

Un sous-tableau est une partie continue d'un tableau. Il peut s'agir d'un seul élément d'un tableau ou d'une fraction du tableau. Le sous-tableau contigu à la plus grande somme signifie un sous-tableau qui a la valeur de somme maximale.

Prenons par exemple le tableau {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Ses sous-tableaux peuvent être {-10, 5, 1, 6}, {5, 1, 6} ou {2, -7, 3, -5}, et ainsi de suite. Cependant, {5, 1, 6, 3} ne peut pas être un sous-tableau car ses éléments ne sont pas contigus.

Vous remarquerez que, parmi tous les sous-tableaux, le sous-tableau mis en évidence {5, 1, 6} a la valeur de somme maximale :

La somme du sous-tableau {5, 1, 6} est égale à 12, soit la somme maximale parmi tous les sous-tableaux possibles du tableau ci-dessus. Par conséquent, pour ce tableau, le sous-tableau contigu de somme maximale est {5, 1, 6}.

Approche simple pour résoudre le problème de la plus grande somme dans un sous-tableau contigu

Le moyen simple de résoudre ce problème consiste à utiliser deux boucles pour rechercher tous les sous-tableaux, calculer la somme, puis trouver sa valeur maximale.

Voici l'organigramme de la méthode simple pour trouver le sous-tableau contigu de somme maximale. Il s'agit d'une méthode exhaustive, car on parcourt tous les sous-tableaux possibles.

Voici les étapes simples pour ce faire.

Étape 1) Initialiser somme_maximale avec la valeur entière minimale et l'ensemble commencer et fin à zéro.

Étape 2) Laisser nous i et j être des indices de tableau où j est supérieur ou égal à i; i marque le début du sous-réseau et j sa fin.

Étape 3) somme_actuelle contient la somme cumulée. Après chaque mise à jour, vérifiez si somme_actuelle est supérieure somme_maximale.

Étape 4) If somme_actuelle est plus grand, remplacer somme_maximale avec elle.

Étape 5) Lorsque vous j atteint la fin du tableau, incrémenter i et réinitialiser somme_actuelle à 0.

Étape 6) Répète jusqu'à i atteint la fin du tableau. somme_maximale contient alors la plus grande somme de sous-tableaux.

Faux Code pour une approche simple

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        store the maximum subArray
    return the maximum sum

C++ Mise en œuvre d'une approche simple

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
    int max_sum = -1e9;
    int begin = 0;
    int end = 0;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += array[j];
            if (max_sum < current_sum) {
                max_sum = current_sum;
                begin = i;
                end = j;
            }
        }
    }
    cout << "largest sum is " << max_sum << endl;
    cout << "largest sum contiguous subarray: ";
    for (int i = begin; i <= end; i++) {
        cout << array[i] << "\t";
    }
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Sortie :

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Mise en œuvre d'une approche simple

def maximumSubarraySum(numbers):
    max_sum, begin, end = -1e9, 0, 0
    for i in range(len(numbers)):
        current_sum = 0
        for j in range(i, len(numbers)):
            current_sum += numbers[j]
            if max_sum < current_sum:
                max_sum = current_sum
                begin, end = i, j
    print("largest sum is ", max_sum)
    print("largest sum contiguous subarray: ", end='')
    for i in range(begin, end + 1):
        print(numbers[i], end='\t')

numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5]
maximumSubarraySum(numbers)

Sortie :

largest sum is 12
largest sum contiguous subarray: 5      1       6

Algorithme de Kadane pour trouver le sous-tableau contigu de somme maximale

L'algorithme de Kadane est une méthode de programmation dynamique qui utilise une seule boucle au lieu de deux. Il traite les tableaux contenant des nombres positifs et négatifs, à condition qu'au moins une valeur soit non négative.

Deux variables suffisent pour trouver le sous-tableau contigu de somme maximale. Voici l'organigramme :

Voici les étapes de l'algorithme de Kadane :

Étape 1) Créez deux variables, somme_actuelle et somme_maximale.

somme_actuelle conserve la somme maximale qui se termine à un index de tableau spécifique, tandis que somme_maximale stocke la plus grande valeur de somme observée jusqu'à présent.

Étape 2) Ajoutez chaque élément du tableau à somme_actuelleVérifiez ensuite les deux conditions ci-dessous :

• If somme_actuelle est inférieur à l'élément actuel, alors somme_actuelle devient l'élément courant.
• If somme_maximale est inférieur à somme_actuelle, puis somme_maximale devient somme_actuelle.

Étape 3) Après avoir répété l'étape précédente pour l'ensemble du tableau, somme_maximale contient le sous-tableau contigu de somme la plus élevée.

Exemple de l'algorithme de Kadane

Nous illustrons l'algorithme de Kadane sur un petit tableau et détaillons chaque étape de la recherche du sous-tableau contigu de somme maximale.

Supposons que le tableau donné ressemble à ceci :

Voici les étapes de l'algorithme de Kadane :

Étape 1) Créez deux variables, somme_actuelle et somme_maximale. Affecter INT_MIN à somme_maximale et zéro à somme_actuelleIci, INT_MIN représente la valeur entière minimale.

Étape 2) À l'indice 0, la valeur est 4. Donc, somme_actuelle = 0 + 4 = 4. Puisque somme_actuelle est plus grand que somme_maximale, somme_maximale devient 4.

Étape 3) À l'indice 1, la valeur est -2. Donc, somme_actuelle = 4 + (-2) = 2.

Ce temps somme_actuelle est inférieur à somme_maximale. Par conséquent, la valeur de somme_maximale n'est pas mis à jour.

Étape 4) La valeur suivante est 1. On l'ajoute à somme_actuelle donne 3. Puisque somme_maximale (4) est toujours supérieur à somme_actuelle, somme_maximale n'est pas mis à jour.

Étape 5) À l'indice 3, la valeur est 3. Incrémentation somme_actuelle par 3 donne somme_actuelle = 6.

Dans ce cas, somme_maximale est plus petit que somme_actuelle, De sorte somme_maximale est mis à jour avec la valeur de somme_actuelle.

Étape 6) Pour le dernier élément du tableau, nous avons -1. En l'ajoutant à somme_actuelle donne 5, ce qui est inférieur à somme_maximale. Alors, somme_maximale reste 6.

Lorsque nous avons atteint la fin du tableau, l'algorithme s'arrête ici. Maintenant, somme_maximale contient la somme maximale, qui est 6. Le sous-tableau est {4, -2, 1, 3}.

Faux Code pour l'algorithme de Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++ Implémentation de l'algorithme de Kadane

#include <iostream>
using namespace std;
void kadane(int array[], int n) {
    int current_sum = 0;
    int max_sum = -1e9;
    // -1e9 means -1,000,000,000
    for (int i = 0; i < n; i++) {
        current_sum += array[i];
        if (max_sum < current_sum) {
            max_sum = current_sum;
        }
        if (current_sum < array[i]) {
            current_sum = array[i];
        }
    }
    cout << "largest sum is " << max_sum << endl;
}
int main() {
    int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
    kadane(array, sizeof(array) / sizeof(array[0]));
}

Sortie :

largest sum is 12

Python Implémentation de l'algorithme de Kadane

def kadane(numbers):
    current_sum = 0
    max_sum = -1e9
    for i in range(len(numbers)):
        current_sum += numbers[i]
        if max_sum < current_sum:
            max_sum = current_sum
        if current_sum < numbers[i]:
            current_sum = numbers[i]
    print("largest sum is ", max_sum)

kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])

Sortie :

largest sum is 12

Analyse de complexité pour le sous-tableau contigu de la plus grande somme

L'approche simple utilise deux boucles pour calculer la somme de chaque sous-tableau possible et trouver la plus grande. Il s'agit d'une approche par force brute ; chaque boucle s'exécute jusqu'à la fin du tableau. tableau, Donner O(N²) le temps.

L'algorithme de Kadane n'utilise qu'une seule boucle, ce qui lui confère une complexité temporelle de O(N) et une complexité spatiale supplémentaire de O(1). Sur un tableau de 100 éléments, la méthode classique effectue 100 × 100 = 10 000 opérations, tandis que l'algorithme de Kadane n'en effectue que 100 — un gain de vitesse considérable pour les grands tableaux.

FAQ