Meditasi LeetCode: Subarray Produk Maksimum

Penerangan untuk Subarray Produk Maksimum ialah:

Memandangkan nombor tatasusunan integer, cari subarray yang mempunyai produk terbesar dan kembalikan produk.

Kes ujian dijana supaya jawapan akan dimuatkan dalam 32-bit integer.

Contohnya:

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.

---

Kini, menggunakan pendekatan kekerasan, kita boleh menyelesaikannya dengan gelung bersarang.

Memandangkan kita akhirnya perlu mendapatkan produk maksimum, mari kita ketahui nilai maksimum dalam tatasusunan dahulu:

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

Kemudian, semasa kita meneliti setiap nombor, kita boleh terus mendarabkannya dengan nombor lain yang tinggal, membina jumlah. Setelah jumlah ini melebihi maksimum, kami boleh mengemas kini maksimum untuk menunjukkan nilai baharu ini:

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

Pada akhirnya, kami hanya boleh mengembalikan maks. Jadi, percubaan pertama penyelesaian akhir kami kelihatan seperti ini:

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

Kerumitan masa dan ruang

Kerumitan masa ialah $O(n^2)$O(n2) kerana kita mempunyai gelung bersarang, melakukan operasi berterusan untuk setiap nombor untuk setiap satu yang kita ulangi.
Kerumitan ruang adalah $O(1)$O(1) kerana kami tidak memerlukan storan tambahan.

Sekali lagi, ini hanyalah percubaan kekerasan. Jadi, mari kita tarik nafas panjang, dan lihat penyelesaian lain.

---

Idea dengan penyelesaian baharu ini adalah untuk mengekalkan dua nilai berbeza untuk maksimum dan minimum semasa kita meneliti setiap nombor dalam tatasusunan. Sebabnya ialah mengendalikan nilai negatif, seperti yang akan kita lihat sebentar lagi.

Pertama, mari kita mulakan dengan memulakan nilai ini: kita akan mempunyai currentMax, currentMin dan hasil, yang semuanya pada mulanya menunjuk kepada nilai pertama dalam tatasusunan:

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

Sekarang, bermula dengan nombor kedua, kami akan mengulangi setiap nilai, mengemas kini nombor maksimum semasa dan nombor minimum semasa serta keputusan (yang akan menjadi maksimum terakhir) semasa kami pergi:

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

Namun, sebelum itu, mari kita lihat contoh perkara yang boleh berlaku jika kita berbuat demikian sahaja.

Katakan tatasusunan kami ialah [-2, 3, -4]. Pada mulanya, currentMax dan currentMin adalah kedua-duanya -2. Kini, untuk mengemas kini currentMax, kami mempunyai dua pilihan: sama ada nombor semasa atau nombor semasa didarab dengan currentMax:

Math.max(3, 3 * -2)

Jelas sekali, ini adalah pilihan pertama, jadi Max semasa kami kini 3.
Untuk mengemas kini currentMin, kami juga mempunyai dua pilihan:

Math.min(3, 3 * -2)

Ia sekali lagi jelas, -6. Buat masa ini, nilai kami kelihatan seperti ini:

currentMax // 3
currentMin // -6

Bersambung ke nombor seterusnya. Kami mempunyai dua pilihan untuk currentMax:

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

Dengan sendirinya, ia mestilah -4, tetapi melihat tatasusunan kami, kami melihat bahawa ini tidak berlaku. Memandangkan mendarab dua nilai negatif menghasilkan nilai positif, Maks semasa kita hendaklah 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.

Atas ialah kandungan terperinci Meditasi LeetCode: Subarray Produk Maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!