Maximum Product Subarray

+10

Multipliez entre eux les éléments d’un sous-tableau de nums, puis renvoyez le produit maximal qu’un sous-tableau peut donner. Un sous-tableau contient des éléments consécutifs, sans interruption, et n’est jamais vide : même un tableau composé de nombres négatifs a donc une réponse. Les zéros et les valeurs négatives sont autorisés.

Fonction

maxProduct(nums: integer-array) → integer

numsinteger-array: les entiers à multiplier, chacun compris entre -10 et 10
Renvoieinteger: le plus grand produit d’un sous-tableau non vide

Contraintes

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Le produit de chaque sous-tableau tient dans un entier signé de 32 bits.

Exemples

Entrée: nums = [2, -5, 3, -2, 0, 4]
Sortie: 60
Explication: Les deux nombres négatifs s’annulent : 2 × -5 × 3 × -2 = 60. Le 0 coupe le tableau en deux, et le 4 de l’autre côté ne peut pas dépasser 60.

Entrée: nums = [-2, 3, -4, -1]
Sortie: 24
Explication: Le produit de tout le tableau est de -24, car il contient trois nombres négatifs. En omettant le dernier élément, il en reste deux : -2 × 3 × -4 = 24, ce qui est supérieur à 12, le résultat obtenu en omettant le premier élément.

Entrée: nums = [-6, 0, -7]
Sortie: 0
Explication: Un sous-tableau qui évite le 0 est constitué d’un seul nombre négatif, et un sous-tableau qui contient le 0 a pour produit 0. Le meilleur choix est le sous-tableau [0].

Pour aller plus loin

Comment indiquer également où commence et où se termine le meilleur sous-tableau, toujours en O(n) et avec un espace de O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La multiplication par un nombre négatif inverse l’ordre des produits : le plus petit produit obtenu jusque-là peut devenir le plus grand à l’étape suivante, et un zéro annule tous les produits. Conserve deux valeurs à chaque indice au lieu d’une seule : le plus grand et le plus petit produit d’un sous-tableau qui se termine à cet indice ; un seul parcours suffit.

Multiplier chaque sous-tableau à partir de chaque position de départ

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixez un indice de départ et déplacez l’indice de fin vers la droite, en multipliant un product courant par chaque nouvel élément. Le comparer au meilleur résultat après chaque étape permet de couvrir chaque sous-tableau une seule fois. Initialisez best avec nums[0], car la réponse peut être négative.

Il y a environ n²/2 paires de début et de fin, avec une multiplication chacune : 2 × 10^8 pour 20 000 éléments.

Algorithme

Définissez best sur nums[0].
Pour chaque start, définissez product sur 1.
Déplacez end de start jusqu’au dernier indice et multipliez product par nums[end].
Si product est supérieur à best, stockez-le.
Renvoyez best.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Parcourir depuis les deux extrémités, en recommençant aux zéros

Intuition

Les zéros divisent le tableau en séquences sans zéro. Dans une séquence, chaque valeur a une valeur absolue d’au moins 1, donc un sous-tableau plus long n’a jamais un produit de valeur absolue plus petite ; seul le signe change. Si le nombre de valeurs négatives est pair, la séquence entière est optimale. S’il est impair, il faut retirer une valeur négative, et la meilleure coupure consiste à retirer la première valeur négative et tout ce qui la précède, ou la dernière valeur négative et tout ce qui la suit. Dans les deux cas, on conserve un suffixe ou un préfixe de la séquence.

Un parcours de gauche à droite, avec un produit courant, vérifie chaque préfixe et le réinitialise à 1 après un 0. Un parcours de droite à gauche vérifie chaque suffixe. Pour [-2, 3, -4, -1], le parcours de gauche à droite voit -2, -6, 24 et -24 ; celui de droite à gauche voit -1, 4, 12 et -24, donc la réponse est 24. Le raisonnement suppose que chaque valeur non nulle a une valeur absolue d’au moins 1, ce qui est le cas pour les entiers.

Algorithme

Définissez best sur nums[0] et product sur 1.
Parcourez de gauche à droite : multipliez product par chaque élément et gardez la plus grande valeur entre best et product.
Chaque fois que product devient 0, remettez-le à 1 pour que le prochain parcours reparte de zéro.
Définissez à nouveau product sur 1 et effectuez le même parcours de droite à gauche.
Renvoyez best.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Suivre le produit le plus grand et le plus petit se terminant ici

Intuition

Chaque sous-tableau se terminant à l’indice i est soit nums[i] seul, soit le produit de nums[i] par un sous-tableau se terminant à i-1. Lorsque nums[i] est négatif, le plus grand de ces produits provient du plus petit produit se terminant à i-1. Il faut donc conserver les deux valeurs : high et low, les produits le plus grand et le plus petit d’un sous-tableau se terminant à l’indice courant. Le nouveau high est le maximum parmi num, high × num et low × num, et le nouveau low est le minimum. Prendre uniquement num permet de recommencer la séquence après un zéro.

Dans le premier exemple, low vaut -30 lorsque -2 arrive, et -30 × -2 = 60 devient high, la réponse.

Algorithme

Définis high, low et best sur nums[0].
Pour chaque élément suivant num, calcule a = high × num et b = low × num.
Définis high comme le plus grand et low comme le plus petit de num, a et b.
Définis best comme le plus grand de best et high.
Retourne best.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

Pièges et cas limites

Ne suivre que le produit le plus grand. Dans le premier exemple, cela renvoie 4 au lieu de 60, car cela élimine le -30 que le -2 transforme en 60.
Calculer le nouveau low à partir de high déjà mis à jour. Enregistrer high × num et low × num avant de modifier l’un ou l’autre.
Initialiser best à 0 ou à 1. [-3] doit renvoyer -3, car le sous-tableau ne peut pas être vide.
N’exécuter que le passage de gauche de la méthode en deux passes. Avec [-2, 3, 4], on ne voit jamais une valeur supérieure à -2, mais le suffixe [3, 4] donne 12.
En JavaScript, TypeScript et Lua, 0 multiplié par un nombre négatif donne -0, qui s’affiche avec un signe moins. Ajouter 0 au résultat avant de le renvoyer.

Questions fréquentes3

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

Le suivi du plus grand et du plus petit produit se terminant à chaque indice prend un temps de O(n) et un espace de O(1). La méthode en deux passes avec préfixe et suffixe a le même coût. Multiplier chaque sous-tableau à partir de chaque position de départ prend un temps de O(n²).

Pourquoi avez-vous besoin du produit minimum dans le sous-tableau de produit maximal ?

Un nombre négatif transforme le produit le plus négatif se terminant à l’index précédent en produit le plus grand. Si tu ne conserves que le produit le plus grand, ce candidat disparaît au moment où tu en as besoin. Dans [3, -2, -4], le plus petit produit avant le -4 est -6, et -6 × -4 = 24 est la réponse.

En quoi le sous-tableau de produit maximal diffère-t-il du sous-tableau maximal ?

Pour les sommes, un total cumulé négatif ne fait que nuire, donc une seule valeur par indice suffit. Pour les produits, une valeur négative cumulée peut devenir la meilleure après un autre nombre négatif, et un zéro réinitialise tout. La version pour les produits conserve donc le plus grand et le plus petit produit à chaque indice.

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

Test #1

Test #2

Test #3

Argument

nums = [2, -5, 3, -2, 0, 4]

Résultat attendu

Maximum Product Subarray

Fonction

Contraintes

Exemples

Indices

Solution

Multiplier chaque sous-tableau à partir de chaque position de départ

Parcourir depuis les deux extrémités, en recommençant aux zéros

Suivre le produit le plus grand et le plus petit se terminant ici

Pièges et cas limites

Questions fréquentes3

Problèmes similaires