Heim Web-Frontend js-Tutorial LeetCode-Meditationen: Maximales Produkt-Subarray

LeetCode-Meditationen: Maximales Produkt-Subarray

Aug 28, 2024 am 06:03 AM

LeetCode Meditations: Maximum Product Subarray

The description for Maximum Product Subarray is:

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

For example:

Input: nums = [2, 3, -2, 4]
Output: 6
Explanation: [2, 3] has the largest product 6.
Nach dem Login kopieren
Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a subarray.
Nach dem Login kopieren

Now, using a brute force approach, we can solve it with a nested loop.

Since we eventually have to get the maximum product, let's first find out the maximum value in the array:

let max = Math.max(...nums);
Nach dem Login kopieren

Then, as we go through each number, we can continually multiply them with the other remaining numbers, building up a total. Once this total is more than max, we can update max to point to this new value:

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;
    }
  }
}
Nach dem Login kopieren

At the end, we can just return max. So, the first attempt of our final solution looks like this:

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;
}
Nach dem Login kopieren

Time and space complexity

The time complexity is O(n2)O(n^2) O(n2) as we have a nested loop, doing a constant operation for each of the numbers for each one we iterate over.
The space complexity is O(1)O(1) O(1) because we don't need additional storage.

Again, this is only a brute force attempt. So, let's take one deep breath, and take a look at another solution.


The idea with this new solution is to keep two different values for the maximum and minimum as we go through each number in the array. The reason for that is handling negative values, as we'll see shortly.

First, let's start with initializing these values: we'll have a currentMax, a currentMin, and a result, all of which are initially pointing to the first value in the array:

let currentMax = nums[0];
let currentMin = nums[0];
let result = nums[0];
Nach dem Login kopieren

Now, starting with the second number, we'll loop through each value, updating the current maximum number and the current minimum number as well as the result (which will be the final maximum) as we go:

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);
}
Nach dem Login kopieren

However, before that, let's see an example of what can happen if we just do that.

Let's say our array is [-2, 3, -4]. Initially, currentMax and currentMin are both -2. Now, to update currentMax, we have two options: it's either the current number or the current number multiplied by currentMax:

Math.max(3, 3 * -2)
Nach dem Login kopieren

Obviously, it's the first option, so our currentMax is now 3.
To update currentMin, we also have two options:

Math.min(3, 3 * -2)
Nach dem Login kopieren

It's again obvious, -6. For now, our values look like this:

currentMax // 3
currentMin // -6
Nach dem Login kopieren

On to the next number. We have two options for currentMax:

Math.max(-4, -4 * 3)
Nach dem Login kopieren

By itself, it has to be -4, but looking at our array, we see that this is not the case. Since multiplying two negative values results in a positive value, our currentMax should be 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)
Nach dem Login kopieren

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];
}
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Time and space complexity

The time complexity for this solution is O(n)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) 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) O(1) since we don't need any additional storage.


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

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Maximales Produkt-Subarray. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Ersetzen Sie Stringzeichen in JavaScript Ersetzen Sie Stringzeichen in JavaScript Mar 11, 2025 am 12:07 AM

Ersetzen Sie Stringzeichen in JavaScript

JQuery überprüfen, ob das Datum gültig ist JQuery überprüfen, ob das Datum gültig ist Mar 01, 2025 am 08:51 AM

JQuery überprüfen, ob das Datum gültig ist

JQuery Get Element Polsterung/Rand JQuery Get Element Polsterung/Rand Mar 01, 2025 am 08:53 AM

JQuery Get Element Polsterung/Rand

10 JQuery Accords Registerkarten 10 JQuery Accords Registerkarten Mar 01, 2025 am 01:34 AM

10 JQuery Accords Registerkarten

10 lohnt 10 lohnt Mar 01, 2025 am 01:29 AM

10 lohnt

HTTP-Debugging mit Knoten und HTTP-Konsole HTTP-Debugging mit Knoten und HTTP-Konsole Mar 01, 2025 am 01:37 AM

HTTP-Debugging mit Knoten und HTTP-Konsole

Benutzerdefinierte Google -Search -API -Setup -Tutorial Benutzerdefinierte Google -Search -API -Setup -Tutorial Mar 04, 2025 am 01:06 AM

Benutzerdefinierte Google -Search -API -Setup -Tutorial

JQuery fügen Sie Scrollbar zu Div hinzu JQuery fügen Sie Scrollbar zu Div hinzu Mar 01, 2025 am 01:30 AM

JQuery fügen Sie Scrollbar zu Div hinzu

See all articles