Méditations LeetCode : sous-tableau de produits maximum

La description du sous-tableau de produits maximum est :

Étant donné un tableau entier nums, trouvez un sous-tableau qui a le plus grand produit et renvoyez le produit.

Les cas de test sont générés de manière à ce que la réponse tienne dans un entier 32 bits.

Par exemple :

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a subarray.

---

Maintenant, en utilisant une approche par force brute, nous pouvons le résoudre avec une boucle imbriquée.

Puisque nous devons finalement obtenir le produit maximum, découvrons d'abord la valeur maximale dans le tableau :

let max = Math.max(...nums);

Ensuite, au fur et à mesure que nous parcourons chaque nombre, nous pouvons continuellement les multiplier par les autres nombres restants, créant ainsi un total. Une fois que ce total est supérieur à max, nous pouvons mettre à jour max pour pointer vers cette nouvelle valeur :

for (let i = 0; i < nums.length; i++) {
  let total = nums[i];
  for (let j = i + 1; j < nums.length; j++) {
    total *= nums[j];
    if (total > max) {
      max = total;
    }
  }
}

À la fin, on peut juste retourner max. Ainsi, la première tentative de notre solution finale ressemble à ceci :

function maxProduct(nums: number[]): number {
  let max = Math.max(...nums);
  for (let i = 0; i < nums.length; i++) {
    let total = nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      total *= nums[j];
      if (total > max) {
        max = total;
      }
    }
  }

  return max;
}

Complexité temporelle et spatiale

La complexité temporelle est $O(n^2)$O(n2) comme nous avons une boucle imbriquée, nous effectuons une opération constante pour chacun des nombres pour chacun sur lequel nous parcourons.
La complexité spatiale est $O(1)$O(1) parce que nous n'avons pas besoin de stockage supplémentaire.

Encore une fois, il ne s’agit que d’une tentative de force brute. Alors, prenons une profonde respiration et examinons une autre solution.

---

L'idée de cette nouvelle solution est de conserver deux valeurs différentes pour le maximum et le minimum au fur et à mesure que nous parcourons chaque nombre du tableau. La raison en est la gestion des valeurs négatives, comme nous le verrons bientôt.

Tout d'abord, commençons par initialiser ces valeurs : nous aurons un currentMax, un currentMin et un résultat, qui pointent tous initialement vers la première valeur du tableau :

let currentMax = nums[0];
let currentMin = nums[0];
let result = nums[0];

Maintenant, en commençant par le deuxième nombre, nous allons parcourir chaque valeur, en mettant à jour le nombre maximum actuel et le nombre minimum actuel ainsi que le résultat (qui sera le maximum final) au fur et à mesure :

for (let i = 1; i < nums.length; i++) {
  currentMax = Math.max(nums[i], nums[i] * currentMax);
  currentMin = Math.min(nums[i], nums[i] * currentMin);

  result = Math.max(result, currentMax);
}

Cependant, avant cela, voyons un exemple de ce qui peut arriver si nous faisons simplement cela.

Disons que notre tableau est [-2, 3, -4]. Initialement, currentMax et currentMin valent tous deux -2. Maintenant, pour mettre à jour currentMax, nous avons deux options : c'est soit le nombre actuel, soit le nombre actuel multiplié par currentMax :

Math.max(3, 3 * -2)

Évidemment, c'est la première option, donc notre currentMax est maintenant 3.
Pour mettre à jour currentMin, nous avons également deux options :

Math.min(3, 3 * -2)

C'est encore une fois évident, -6. Pour l'instant, nos valeurs ressemblent à ceci :

currentMax // 3
currentMin // -6

Passons au numéro suivant. Nous avons deux options pour currentMax :

Math.max(-4, -4 * 3)

En soi, il doit être de -4, mais en regardant notre tableau, on voit que ce n'est pas le cas. Puisque la multiplication de deux valeurs négatives donne une valeur positive, notre currentMax devrait être 24 (-2 * 3 * -4).

Note

If we were to multiply it with currentMin, we reach this value: -4 * -6 = 24.

Also, let's look at our currentMin options:

Math.min(-4, -4 * -6)

This has to be -4 again, but something feels off.

The catch is that when we have negative numbers consecutively, our sign alternates, which affects the maximum result we need. That's why we're keeping track of the minimum value in the first case: to keep track of the sign.

Since the issue is just alternating signs, we can simply swap the maximum and minimum values when we're looking at a negative number before updating those values:

if (nums[i] < 0) {
  [currentMax, currentMin] = [currentMin, currentMax];
}

Also, note that we're taking the product of each previous subarray as we go, essentially solving a smaller portion of the problem.

And that's it, our final solution looks like this:

function maxProduct(nums: number[]): number {
  let currentMax = nums[0];
  let currentMin = nums[0];
  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < 0) {
      [currentMax, currentMin] = [currentMin, currentMax];
    }

    currentMax = Math.max(nums[i], nums[i] * currentMax);
    currentMin = Math.min(nums[i], nums[i] * currentMin);

    result = Math.max(result, currentMax);
  }

  return result;
}

Time and space complexity

The time complexity for this solution is $O(n)$O(n) because we go through each number once doing a constant operation.

Note

Math.max() and Math.min() are constant operations here, since we're comparing two values only. However, if we were to find max or min of a whole array, it would be $O(n)$O(n) as the time complexity of the operation would increase proportionately to the size of the array.

The space complexity is $O(1)$O(1) since we don't need any additional storage.

---

The next problem on the list is called Word Break. Until then, happy coding.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!