Maximum Subarray

+10

On vous donne une liste d’entiers nums. Un sous-tableau est une suite d’éléments voisins, sans interruption, et il doit contenir au moins un élément. Renvoyez la plus grande somme que peut avoir un sous-tableau de nums. Vous renvoyez uniquement la somme, pas le sous-tableau lui-même.

Fonction

maxSubArray(nums: integer-array) → integer

numsinteger-array: la liste d’entiers, avec au moins un élément
Renvoieinteger: la plus grande somme d’une séquence non vide d’éléments adjacents

Contraintes

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
La réponse tient toujours dans un entier signé de 32 bits.

Exemples

Entrée: nums = [2, -4, 3, -1, 5, -6, 1]
Sortie: 7
Explication: La séquence [3, -1, 5] totalise 7. En l'étendant vers la gauche, on ajoute -4 puis 2, soit une perte nette de 2. En l'étendant vers la droite, on ajoute -6 puis 1, soit une perte nette de 5. Aucune autre séquence ne fait mieux.

Pour aller plus loin

Peux-tu aussi le résoudre par diviser pour régner en O(n log n), en scindant la liste en deux et en traitant les séquences qui traversent le milieu ?

Solution

Une liste de n nombres contient environ n²/2 sous-tableaux, trop nombreux pour les vérifier un par un lorsqu’elle comporte 10^5 éléments. La difficulté vient des nombres négatifs : une séquence doit conserver un élément négatif si ce qui suit compense sa valeur, et tout abandonner avant lui dans le cas contraire. L’algorithme de Kadane fait ce choix à chaque élément à l’aide d’une seule comparaison.

Sommer chaque sous-tableau

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque sous-tableau a un premier indice left et un dernier indice right ; essayer chaque paire permet donc de trouver le meilleur. Fixe left et avance right, en ajoutant chaque nouvel élément à un total cumulé : chaque sous-tableau ne nécessite qu’une addition, sans troisième boucle.

Il reste tout de même environ n²/2 paires, soit cinq milliards d’additions pour 10^5 éléments.

Algorithme

Définis best comme le premier élément.
Pour chaque indice de départ left, définis un total cumulatif à 0.
Déplace right de left jusqu’à la fin de la liste et ajoute nums[right] à total.
Après chaque addition, stocke total dans best s’il est plus grand.
Renvoie best.

def maxSubArray(nums):
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        # Grow the subarray that starts at left by one element at a time
        for right in range(left, len(nums)):
            total += nums[right]
            best = max(best, total)
    return best

Algorithme de Kadane

Intuition

La meilleure séquence se terminant à l’indice i est soit nums[i] seul, soit la meilleure séquence se terminant à i-1, à laquelle on ajoute nums[i], puisqu’aucune autre séquence se terminant à i-1 n’a une somme plus grande. On conserve donc un nombre, endingHere, qui représente la meilleure somme d’une séquence se terminant à l’élément courant. À l’élément suivant x, il devient la plus grande valeur entre x et endingHere + x : tant que la somme de la séquence est positive, on la prolonge, et dès qu’elle est nulle ou négative, on recommence à partir de x.

Le meilleur sous-tableau se termine quelque part : la réponse est donc la plus grande valeur prise par endingHere. Dans le premier exemple, il prend les valeurs 2, -2, 3, 2, 7, 1, 2, et la réponse est 7.

Algorithme

Définissez endingHere et best sur le premier élément.
Pour chaque élément suivant x, définissez endingHere sur la plus grande valeur entre x et endingHere + x.
Définissez best sur la plus grande valeur entre best et endingHere.
Après le dernier élément, renvoyez best.

def maxSubArray(nums):
    current = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

Pièges et cas limites

Commencer best à 0. [-3, -1, -2] renvoie alors 0 au lieu de -1. Commencez par le premier élément.
Ramener la somme courante à max(0, endingHere + x). Cela échoue sur la même liste ; comparez plutôt avec x.
Additionner uniquement les nombres positifs. Les éléments doivent être adjacents, donc le premier exemple donne 7, et non 2 + 3 + 5 + 1 = 11.
Commencer la boucle à l’index 1 sans définir endingHere et best à nums[0]. Une liste d’un seul élément, comme [-5], doit renvoyer -5.

Questions fréquentes3

Qu’est-ce que l’algorithme de Kadane ?

L'algorithme de Kadane trouve la plus grande somme d'un sous-tableau contigu en une seule passe. Il conserve la meilleure somme d'une séquence se terminant à l'élément courant et, à chaque nouvel élément, prolonge cette séquence ou en commence une nouvelle. La plus grande de ces sommes est la réponse.

Quelle est la complexité temporelle du sous-tableau maximal ?

L’algorithme de Kadane s’exécute en O(n) et utilise O(1) d’espace supplémentaire, car chaque élément est examiné une seule fois. Vérifier chaque sous-tableau en maintenant un total cumulatif prend O(n²), et recalculer la somme de chaque sous-tableau depuis zéro prend O(n³).

Pourquoi le sous-tableau maximal est-il un problème de programmation dynamique ?

La meilleure somme d’une séquence se terminant à l’indice i dépend uniquement de la meilleure somme d’une séquence se terminant à l’indice i-1. Il s’agit d’une récurrence sur les indices, caractéristique de la programmation dynamique. L’algorithme de Kadane ne conserve que la valeur la plus récente au lieu d’un tableau entier ; il nécessite donc un espace O(1).

def maxSubArray(nums):
    # Écrivez le code ici

Test #1

Test #2

Argument

nums = [2, -4, 3, -1, 5, -6, 1]

Résultat attendu