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

最後に、最大値を返すだけです。したがって、最終的な解決策の最初の試行は次のようになります:

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) 追加のストレージが必要ないからです。

繰り返しますが、これは単なる強引な試みです。それでは、一度深呼吸して、別の解決策を見てみましょう。

---

この新しいソリューションのアイデアは、配列内の各数値を調べるときに最大値と最小値の 2 つの異なる値を保持することです。その理由は、後で説明するように、負の値を処理するためです。

まず、これらの値の初期化から始めましょう。currentMax、currentMin、結果が得られます。これらはすべて、最初は配列内の最初の値を指します。

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

次に、2 番目の数値から始めて、各値をループし、現在の最大値と現在の最小値、および結果 (最終的な最大値) を更新します。

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 を更新するには、2 つのオプションがあります。現在の数値、または現在の数値に currentMax を乗算した値です。

Math.max(3, 3 * -2)

明らかに、これが最初のオプションなので、currentMax は 3 になります。
currentMin を更新するには、次の 2 つのオプションもあります:

Math.min(3, 3 * -2)

これもまた明らかです、-6。現時点では、値は次のようになります:

currentMax // 3
currentMin // -6

次の番号へ。 currentMax には 2 つのオプションがあります:

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

それ自体は -4 でなければなりませんが、配列を見るとそうではないことがわかります。 2 つの負の値を乗算すると正の値が得られるため、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 中国語 Web サイトの他の関連記事を参照してください。