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

Quel est le sous-tableau contigu à la plus grande somme ?

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.

Par exemple, un tableau est {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Ses sous-tableaux peuvent être : {-10,5,1,6} ou {5,1,6} ou {2,7,3, -5} etc. Mais {5,1,6,3} ne peut pas être un sous-tableau car ils ne maintiennent pas les séquences.

Si vous remarquez, parmi tous les sous-tableaux, le sous-tableau en surbrillance suivant (5,1,6) a la valeur de sommation maximale :

La somme du sous-tableau {5,1,6} = 11, est la somme maximale de toutes les combinaisons possibles de sous-tableau du tableau ci-dessus. Ainsi, pour le tableau ci-dessus, le sous-tableau maximum est {5,1,6}.

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

Approche simple pour résoudre le sous-tableau contigu à la plus grande somme

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 l'approche simple permettant de trouver le sous-tableau contigu à la plus grande somme. Il s'agit d'une approche par force brute, car nous passons en revue tous les sous-réseaux possibles.

Voici les étapes simples pour ce faire.

Étape 1) Initialisez le max_sum avec une valeur entière minimale et attribuez aux variables « begin » et « end » avec zéro.

Étape 2) Soit i et j l'index du tableau, où « j » est supérieur ou égal à « i ». Il représente l'index de début du sous-tableau et « j » représente l'index de fin du sous-tableau.

Étape 3) « Current_sum » contiendra la somme du sous-tableau. Après avoir calculé la somme actuelle, vérifiez si current_sum est supérieur à max_sum.

Étape 4) Si current_sum est supérieur, remplacez max_sum par la somme actuelle.

Étape 5) Vérifiez si « j » atteint la fin du tableau ou non. Si « j » atteint la fin du tableau, incrémentez alors « i » et modifiez la valeur current_sum à 0.

Étape 6) Effectuez toutes ces étapes, jusqu'à ce que « i » atteigne la fin du tableau.

Étape 7) À la fin de ces deux boucles, max_sum contiendra la plus grande somme de sous-tableau.

Pseudo Code pour une approche simple

  function maximumSubarraySum():
    input: array
  for all possible subArray from array:
    calculate sum of each sub array
    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 à la plus grande somme

L'algorithme de Kadane est une sorte de méthode de « programmation dynamique ». Ici, nous utiliserons une boucle au lieu de deux boucles. L'implémentation générale de l'algorithme de Kadane ne fonctionne que pour les tableaux de nombres positifs.

Nous n’avons besoin que de deux variables pour trouver le sous-tableau contigu à la plus grande somme. Voici l'organigramme de l'algorithme de Kadane :

Voici les étapes de l'algorithme de Kadane :

Étape 1) Créez deux variables, current_sum et max_sum.

« Current_sum » conservera la valeur de la somme maximale qui se termine par un index de tableau spécifique, tandis que « max_sum » stockera la valeur de sommation maximale jusqu'à présent.

Étape 2) Nous ajouterons la valeur avec le current_sum pour chaque élément du tableau. Ensuite, nous vérifierons deux conditions ci-dessous :

• Si current_sum est inférieur à l'élément actuel, alors la valeur current_sum sera l'élément actuel.
• Si max_sum est inférieur à current_sum, alors max_sum sera current_sum.

Étape 3) En effectuant l'étape précédente pour l'ensemble du tableau, nous aurons le sous-tableau contigu à la plus grande somme dans la variable « max_sum ».

Exemple de l'algorithme de Kadane

Nous démontrerons l'algorithme de Kadanes avec un tableau de petite taille et discuterons de chaque étape de la recherche du sous-tableau contigu à la plus grande somme.

Supposons que le tableau donné ressemble à ceci :

Voici les étapes de l'algorithme de Kadane :

Étape 1) Créez deux variables, current_sum et max_sum. Attribuez INT_MIN à max_sum et zéro à current_sum. (Ici, INT_MIN signifie le nombre entier minimum).

Étape 2) À l'index 0, la valeur est 4. Ainsi, la somme_actuelle = 0 + 4 ou 4. Ici, la somme_actuelle est plus grande que la somme_maximale, la somme_maximale sera 4.

Étape 3) A l'index 1, la valeur est -2. Ainsi, la somme_actuelle = 4 + (-2) ou 2.

Cette fois, current_sum est inférieur à max_sum. Par conséquent, la valeur de max_sum ne sera pas mise à jour.

Étape 4) La valeur suivante est 1. Si nous ajoutons cela avec current_sum, alors current_sum sera 3. Pourtant, max_sum est supérieur à current_sum. Ainsi, le max_sum ne sera pas mis à jour.

Étape 5) À l'indice 3, la valeur est trois. Nous mettrons à jour la valeur en incrémentant current_sum de 3. Ainsi, current_sum sera 6.

Dans ce cas, max_sum est inférieur à current_sum. Ainsi, max_sum sera mis à jour avec la valeur de current_sum.

Étape 6) Pour le dernier élément du tableau, nous avons -1. Si nous ajoutons cela avec current_sum, current_sum sera 5, ce qui est plus petit que max_sum. Ainsi, le max_sum restera 6.

Lorsque nous atteignons la fin du tableau, l’algorithme se termine ici. Désormais, « max_sum » contient le sous-tableau de somme maximale. Ce qui vaut 5. Le sous-tableau est {4,-2,1,3}.

Pseudo-code pour l'algorithme de Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements 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 -10000000
  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. Cette méthode calcule toutes les sommes de sous-tableaux possibles pour trouver la plus grande. C'est une approche par force brute. Chaque boucle s'étend jusqu'à la fin du tableau.

Si un tableau a un total de N éléments, puis à l'aide de deux boucles, nous passerons par N² éléments. En conséquence, la complexité temporelle d’une approche simple pour trouver le sous-tableau contigu à la plus grande somme sera O(N2). Ici, « O » signifie la fonction de complexité.

D'autre part, l'algorithme de Kadane est la méthode de programmation dynamique permettant de trouver le sous-tableau de somme contigu maximum. Si vous suivez l'exemple ou le code, vous verrez que nous n'utilisons qu'une seule boucle.

Par conséquent, si le tableau d’entrée a une taille de N, alors la complexité temporelle de l'algorithme de Kadane sera O(N). C’est plus rapide que l’approche simple. Par exemple, un tableau contenant 100 éléments. L'approche simple prendra 100*100 ou 10,000 100 temps CPU. Mais l'algorithme de Kadane ne prendra que temps CPU.