algorithm
Algorithme de sous-tableau maximum

Algorithme du sous-tableau maximum Informations de base

Le problème du sous-tableau maximum est la méthode permettant de trouver le sous-tableau contigu dans un tableau de nombres à une dimension ayant la plus grande somme.

Le problème a été proposé à l'origine par Ulf Grenander de l'Université Brown en 1977, en tant que modèle simplifié pour l'estimation du maximum de vraisemblance des motifs dans les images numérisées.

Nous pouvons avoir un problème comme celui-ci, considérons une liste de différents entiers. Nous pourrions être intéressés par le sous-ensemble complètement adjacent qui aura la plus grande somme. Par exemple, si nous avons le tableau [0, 1, 2, -2, 3, 2] , le sous-tableau maximal est [3, 2] , avec une somme de 5 .

Approche Brute-Force pour la solution:

Cette méthode est la plus inefficace pour trouver la solution. En cela, nous finirons par parcourir chaque sous-tableau possible, puis trouver la somme de tous. Enfin, comparez toutes les valeurs et trouvez le sous-tableau maximum.

Pseudo-code pour l’approche de la force brutale:

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

La complexité temporelle de la méthode Brute-Force est O(n^2) . Alors passons à diviser et à conquérir l'approche.

Approche de division et de conquête pour la solution:

Trouvez la somme des sous-réseaux à gauche, les sous-réseaux à droite. Jetez ensuite un coup d’œil à tous ceux qui traversent la ligne de partage des centres et retournez la somme maximale. Comme il s’agit d’un algorithme de division et de conquête, nous devons avoir deux fonctions différentes.

La première est une étape de division,

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

Dans la deuxième partie, séparez les différentes parties créées dans la première partie.

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

La complexité temporelle de la méthode Divide and Conquer est O(nlogn) . Passons donc à l'approche de la programmation dynamique.

Approche de programmation dynamique:

Cette solution est également connue sous le nom d'Algorithme de Kadane. C'est un algorithme de temps linéaire. Cette solution est donnée par Joseph B. Kadane à la fin des années 70.

Cet algorithme ne fait que passer par la boucle, modifiant continuellement la somme maximale actuelle. Il est intéressant de noter que ceci est un exemple très simple d'algorithme de programmation dynamique, car il prend un problème de chevauchement et le réduit pour que nous puissions trouver une solution plus efficace.

Pseudo-code de l'algorithme de Kadane:

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

La complexité temporelle de l'algorithme de Kadane est O(n) .

Implémentation C #

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}