LeetCode 冥想：最大乘积子数组

最大乘积子数组的描述是：

给定一个整数数组 nums，找到一个具有最大乘积的子数组，并返回乘积。

生成测试用例，以便答案适合32位整数。

例如：

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.

---

现在，使用暴力方法，我们可以通过嵌套循环来解决它。

由于我们最终要得到最大的乘积，所以我们首先找出数组中的最大值：

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

然后，当我们遍历每个数字时，我们可以不断地将它们与其他剩余的数字相乘，建立一个总数。一旦这个总数超过 max，我们就可以更新 max 以指向这个新值：

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;
    }
  }
}

最后，我们可以返回 max。因此，我们最终解决方案的第一次尝试如下所示：

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;
}

时间和空间复杂度

时间复杂度为 $O(n^2)$O(n2） 因为我们有一个嵌套循环，所以对我们迭代的每个数字的每个数字进行常量运算。
空间复杂度为 $O(1)$O(1) 因为我们不需要额外的存储空间。

再说一遍，这只是一次暴力尝试。那么，让我们深吸一口气，看看另一种解决方案。

---

这个新解决方案的想法是在我们遍历数组中的每个数字时保留两个不同的最大值和最小值。原因是处理负值，我们很快就会看到。

首先，让我们从初始化这些值开始：我们将有一个 currentMax、一个 currentMin 和一个结果，所有这些最初都指向数组中的第一个值：

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

现在，从第二个数字开始，我们将循环遍历每个值，更新当前最大数字和当前最小数字以及结果（这将是最终的最大值）：

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);
}

但是，在此之前，让我们看一个例子，看看如果我们这样做会发生什么。

假设我们的数组是 [-2, 3, -4]。最初，currentMax 和 currentMin 均为 -2。现在，要更新 currentMax，我们有两个选择：要么是当前数字，要么是当前数字乘以 currentMax：

Math.max(3, 3 * -2)

显然，这是第一个选项，所以我们的 currentMax 现在是 3。
要更新 currentMin，我们还有两个选择：

Math.min(3, 3 * -2)

这又是显而易见的，-6。目前，我们的值如下所示：

currentMax // 3
currentMin // -6

转到下一个号码。对于 currentMax，我们有两个选项：

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

它本身必须是-4，但是看看我们的数组，我们发现情况并非如此。由于两个负值相乘会得到正值，因此我们的 currentMax 应为 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.

以上是LeetCode 冥想：最大乘积子数组的详细内容。更多信息请关注PHP中文网其他相关文章！