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}n2$22 🎜>)O(n^2) O(nO(nn
$2\mathrm{）}的每個數字進行常數運算。$ 空間複雜度為 O

(

---

1

)

1

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

)

O(1)

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

O(1)

Math.max(3, 3 * -2)

因為我們不需要額外的儲存空間。

再說一次，這只是暴力嘗試。那麼，讓我們深吸一口氣，看看另一個解決方案。

Math.min(3, 3 * -2)

這個新解決方案的想法是在我們遍歷數組中的每個數字時保留兩個不同的最大值和最小值。原因是處理負值，我們很快就會看到。

首先，讓我們先從初始化這些值開始：我們將有一個 currentMax、一個 currentMin 和一個結果，所有這些最初都指向數組中的第一個值：

currentMax // 3
currentMin // -6

現在，從第二個數字開始，我們將循環遍歷每個值，更新當前最大數字和當前最小數字以及結果（這將是最終的最大值）：

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

但是，在此之前，讓我們先來看一個例子，看看如果我們這樣做會發生什麼。

Note

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

假設我們的陣列是 [-2, 3, -4]。最初，currentMax 和 currentMin 均為 -2。現在，要更新 currentMax，我們有兩個選擇：要么是當前數字，要么是當前數字乘以 currentMax： 顯然，這是第一個選項，所以我們的 currentMax 現在是 3。 要更新 currentMin，我們還有兩個選擇： 這又是顯而易見的，-6。目前，我們的價值觀是這樣的： 轉到下一個號碼。對於 currentMax，我們有兩個選項： 它本身必須是-4，但是看看我們的數組，我們發現情況並非如此。由於兩個負值相乘會得到正值，因此我們的 currentMax 應為 24 (-2 * 3 * -4)。

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中文網其他相關文章！