Problème maximal de sous-matrice en Java

1. Vue d'ensemble

Le problème de sous-tableau maximal est une tâche pour trouver la série d'éléments contigus avec la somme maximale dans un tableau donné.

Par exemple, dans le tableau ci-dessous, le sous-tableau en surbrillance a la somme maximale (6):

Dans ce didacticiel, nous examinerons deux solutions pour trouver le sous-tableau maximal dans un tableau . Un dont nous allons concevoir avec O (n) complexité de temps et d'espace.

2. Algorithme de force brute

La force brute est une approche itérative pour résoudre un problème. Dans la plupart des cas, la solution nécessite un certain nombre d'itérations sur une structure de données. Dans les prochaines sections, nous appliquerons cette approche pour résoudre le problème maximal du sous-tableau.

2.1. Approche

D'une manière générale, la première solution qui me vient à l'esprit est de calculer la somme de chaque sous-tableau possible et de renvoyer celui avec la somme maximale.

Pour commencer, nous allons calculer la somme de chaque sous-tableau qui commence à l'index 0. Et de même, nous trouverons tous les sous-tableaux commençant à chaque index de 0 à n-1n est la longueur du tableau:

Nous allons donc commencer à l'index 0 et ajouter chaque élément à la somme en cours dans l'itération. Nous garderons également une trace de la somme maximale observée jusqu'à présent . Cette itération est affichée sur le côté gauche de l'image ci-dessus.

Sur le côté droit de l'image, nous pouvons voir l'itération qui commence à l'index 3 . Dans la dernière partie de cette image, nous avons le sous-tableau avec la somme maximale entre les index 3 et 6 .

Cependant, notre algorithme continuera à trouver tous les sous-tableaux commençant à des indices compris entre 0 et n-1 .

2.2. la mise en oeuvre

Voyons maintenant comment nous pouvons implémenter cette solution en Java:

public int maxSubArray(int[] nums) { int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left < n; left++) { int runningWindowSum = 0; for (int right = left; right  maximumSubArraySum) { maximumSubArraySum = runningWindowSum; start = left; end = right; } } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maximumSubArraySum; }

Comme prévu, nous mettons à jour le maximumSubArraySum si la somme actuelle est supérieure à la somme maximale précédente. Notamment, nous mettons également à jour le début et la fin pour connaître les emplacements d'index de ce sous-tableau .

2.3. Complexité

De manière générale, la solution de force brute effectue plusieurs itérations sur le tableau afin d'obtenir toutes les solutions possibles. Cela signifie que le temps pris par cette solution augmente de façon quadratique avec le nombre d'éléments dans le tableau. Cela peut ne pas être un problème pour les tableaux de petite taille. Mais à mesure que la taille du tableau augmente, cette solution n'est pas efficace.

En inspectant le code, nous pouvons également voir qu'il y a deux boucles for imbriquées . Par conséquent, nous pouvons conclure que la complexité temporelle de cet algorithme est O (n2) .

Dans les sections suivantes, nous résoudrons ce problème en complexité O (n) en utilisant la programmation dynamique.

3. Programmation dynamique

La programmation dynamique résout un problème en le divisant en sous-problèmes plus petits. Ceci est très similaire à la technique de résolution d'algorithme de division et de conquête. La principale différence, cependant, est que la programmation dynamique ne résout un sous-problème qu'une seule fois.

Il stocke ensuite le résultat de ce sous-problème et réutilise ultérieurement ce résultat pour résoudre d'autres sous-problèmes connexes. Ce processus est connu sous le nom de mémorisation .

3.1. Algorithme de Kadane

L'algorithme de Kadane est une solution populaire au problème de sous-matrice maximum et cette solution est basée sur la programmation dynamique.

Le défi le plus important dans la résolution d'un problème de programmation dynamique est de trouver les sous-problèmes optimaux .

3.2. Approche

Comprenons ce problème d'une manière différente:

Dans l'image ci-dessus, nous supposons que le sous-tableau maximum se termine au dernier emplacement d'index. Par conséquent, la somme maximale du sous-tableau sera:

maximumSubArraySum = max_so_far + arr[n-1]

max_so_far est la somme maximale d'un sous-tableau qui se termine à l'index n-2 . Ceci est également montré dans l'image ci-dessus.

Maintenant, nous pouvons appliquer cette hypothèse à n'importe quel index du tableau. Par exemple, la somme maximale du sous-tableau qui se termine à n-2 peut être calculée comme suit:

maximumSubArraySum[n-2] = max_so_far[n-3] + arr[n-2]

Par conséquent, nous pouvons conclure que:

maximumSubArraySum[i] = maximumSubArraySum[i-1] + arr[i]

Maintenant, puisque chaque élément du tableau est un sous-tableau spécial de taille un, nous devons également vérifier si un élément est supérieur à la somme maximale elle-même:

maximumSubArraySum[i] = Max(arr[i], maximumSubArraySum[i-1] + arr[i])

En regardant ces équations, nous pouvons voir que nous devons trouver la somme maximale du sous-tableau à chaque index du tableau. Ainsi, nous avons divisé notre problème en n sous-problèmes. Nous pouvons trouver la somme maximale à chaque index en itérant le tableau une seule fois:

L'élément en surbrillance montre l'élément actuel dans l'itération. À chaque index, nous appliquerons l'équation dérivée précédemment pour calculer une valeur pour max_ending_here . Cela nous aide à identifier si nous devons inclure l'élément actuel dans le sous-tableau ou démarrer un nouveau sous-tableau à partir de cet index .

Another variable, max_so_far is used to store the maximum subarray sum found during the iteration. Once we iterate over the last index, max_so_far will store the sum of the maximum subarray.

3.3. Implementation

Again, let's see how we can now implement the Kadane algorithm in Java, following the above approach:

public int maxSubArraySum(int[] arr) {       int size = arr.length;     int start = 0;     int end = 0;       int maxSoFar = 0, maxEndingHere = 0;       for (int i = 0; i  maxEndingHere + arr[i]) {             start = i;             maxEndingHere = arr[i];         } else             maxEndingHere = maxEndingHere + arr[i];           if (maxSoFar < maxEndingHere) {             maxSoFar = maxEndingHere;             end = i;         }     } logger.info("Found Maximum Subarray between {} and {}", start, end);     return maxSoFar; }

Here, we updated the start and end to find the maximum subarray indices.

3.4. Complexity

Since we only need to iterate the array once, the time complexity of this algorithm is O(n).

So as we can see, the time taken by this solution grows linearly with the number of elements in the array. Consequently, it is more efficient than the brute force approach we discussed in the last section.

4. Conclusion

Dans ce tutoriel rapide, nous avons décrit deux façons de résoudre le problème de sous-tableau maximal.

Tout d'abord, nous avons exploré une approche de la force brute et avons vu que cette solution itérative aboutissait à un temps quadratique. Plus tard, nous avons ensuite discuté de l'algorithme de Kadane et utilisé la programmation dynamique pour résoudre le problème en temps linéaire.

Comme toujours, le code source complet de l'article est disponible à l'adresse over sur GitHub.