Maximum Product Subarray

+10

Multipliziere die Elemente eines Teilarrays von nums miteinander und gib das größte Produkt zurück, das ein Teilarray ergeben kann. Ein Teilarray besteht aus aufeinanderfolgenden Elementen ohne Lücken und ist niemals leer, daher gibt es auch bei einem Array aus negativen Zahlen eine Antwort. Nullen und negative Werte sind zulässig.

Funktion

maxProduct(nums: integer-array) → integer

numsinteger-array: die zu multiplizierenden ganzen Zahlen, jeweils zwischen -10 und 10
Gibt zurückinteger: das größte Produkt eines nicht leeren Teilarrays

Einschränkungen

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Das Produkt jedes Teilarrays passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl.

Beispiele

Eingabe: nums = [2, -5, 3, -2, 0, 4]
Ausgabe: 60
Erklärung: Die beiden negativen Zahlen heben sich gegenseitig auf: 2 × -5 × 3 × -2 = 60. Die 0 teilt das Array in zwei Teile, und die 4 auf der anderen Seite kann 60 nicht übertreffen.

Eingabe: nums = [-2, 3, -4, -1]
Ausgabe: 24
Erklärung: Das gesamte Array ergibt als Produkt -24, weil es drei negative Zahlen enthält. Lässt man das letzte Element weg, bleiben zwei davon übrig: -2 × 3 × -4 = 24, was größer ist als die 12, die man erhält, wenn man das erste Element weglässt.

Eingabe: nums = [-6, 0, -7]
Ausgabe: 0
Erklärung: Ein Teilarray, das die 0 vermeidet, ist eine einzelne negative Zahl, und ein Teilarray, das die 0 enthält, ergibt beim Multiplizieren 0. Die beste Wahl ist das Teilarray [0].

Weiterführende Frage

Wie würdest du außerdem angeben, wo das beste Teilarray beginnt und endet, und das weiterhin in O(n) Zeit und mit O(1) Speicherplatz?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Multiplikation mit einer negativen Zahl kehrt die Reihenfolge der Produkte um, sodass das bisher kleinste Produkt einen Schritt später zum größten werden kann, und eine Null setzt alle Produkte auf null. Führe an jedem Index zwei Werte statt einem mit: das größte und das kleinste Produkt eines Teilarrays, das dort endet. Ein einziger Durchlauf genügt.

Multipliziere jedes Teilarray von jedem Startpunkt aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Lege einen Startindex fest und verschiebe das Ende nach rechts, wobei du ein laufendes product mit jedem neuen Element multiplizierst. Wenn du es nach jedem Schritt mit dem bisherigen Bestwert vergleichst, wird jedes Teilarray genau einmal berücksichtigt. Setze best auf nums[0], da das Ergebnis negativ sein kann.

Es gibt etwa n²/2 Start-Ende-Paare mit jeweils einer Multiplikation: 2 × 10^8 für 20.000 Elemente.

Algorithmus

Setze best auf nums[0].
Setze für jedes start product auf 1.
Bewege end von start bis zum letzten Index und multipliziere product mit nums[end].
Speichere product, wenn es größer als best ist.
Gib best zurück.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Von beiden Enden aus scannen und bei Nullen neu beginnen

Idee

Nullen teilen das Array in nullfreie Abschnitte auf. Innerhalb eines Abschnitts ist jeder Wert betragsmäßig mindestens 1, daher hat ein längeres Teilarray niemals ein kleineres Absolutprodukt; nur das Vorzeichen ändert sich. Bei einer geraden Anzahl negativer Zahlen ist der ganze Abschnitt optimal. Bei einer ungeraden Anzahl muss eine negative Zahl entfernt werden, und der beste Schnitt entfernt die erste negative Zahl und alles davor oder die letzte negative Zahl und alles danach. In beiden Fällen behältst du ein Suffix oder ein Präfix des Abschnitts.

Ein Durchlauf von links mit einem laufenden Produkt prüft jedes Präfix und setzt das Produkt nach einer 0 auf 1 zurück. Ein Durchlauf von rechts prüft jedes Suffix. Bei [-2, 3, -4, -1] sieht der Durchlauf von links -2, -6, 24 und -24, der von rechts -1, 4, 12 und -24; die Antwort ist also 24. Das Argument setzt voraus, dass jeder Wert ungleich null betragsmäßig mindestens 1 ist, was für Ganzzahlen gilt.

Algorithmus

Setze best auf nums[0] und product auf 1.
Gehe von links nach rechts: Multipliziere product mit jedem Element und behalte den größeren Wert von best und product.
Wenn product 0 wird, setze es wieder auf 1, damit der nächste Durchlauf neu beginnt.
Setze product erneut auf 1 und gehe genauso von rechts nach links.
Gib best zurück.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Verfolge das größte und kleinste Produkt, das hier endet

Idee

Jedes Teilarray, das am Index i endet, besteht entweder nur aus nums[i] oder aus nums[i] multipliziert mit einem Teilarray, das bei i-1 endet. Wenn nums[i] negativ ist, stammt das größte dieser Produkte vom kleinsten Produkt, das bei i-1 endet. Behalte also beide Werte im Blick: high und low, die größten und kleinsten Produkte eines Teilarrays, das am aktuellen Index endet. Der neue Wert von high ist der größte aus num, high × num und low × num, und der neue Wert von low ist der kleinste. Nur num zu nehmen, startet die Folge nach einer Null neu.

Im ersten Beispiel ist low gleich -30, wenn die -2 hinzukommt, und -30 × -2 = 60 wird zu high, der Antwort.

Algorithmus

Setze high, low und best auf nums[0].
Berechne für jedes spätere Element num a = high × num und b = low × num.
Setze high auf den größten und low auf den kleinsten Wert aus num, a und b.
Setze best auf den größeren Wert aus best und high.
Gib best zurück.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

Stolperfallen und Grenzfälle

Nur das größte Produkt nachverfolgen. Beim ersten Beispiel wird dadurch 4 statt 60 zurückgegeben, weil -30 verworfen wird, aus dem durch -2 60 wird.
low aus dem bereits aktualisierten high berechnen. Speichere high × num und low × num, bevor du einen der beiden Werte änderst.
best mit 0 oder 1 initialisieren. [-3] muss -3 zurückgeben, da das Teilarray nicht leer sein darf.
Nur den Durchlauf von links nach rechts der Methode mit zwei Durchläufen ausführen. Bei [-2, 3, 4] sieht sie nie einen Wert größer als -2, aber das Suffix [3, 4] ergibt 12.
In JavaScript, TypeScript und Lua ist 0 mal eine negative Zahl -0, was mit einem Minuszeichen ausgegeben wird. Addiere vor der Rückgabe 0 zum Ergebnis.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Maximum-Product-Subarray-Problems?

Das Verfolgen des größten und kleinsten Produkts, das an jedem Index endet, benötigt O(n) Zeit und O(1) Speicherplatz. Die Methode mit Präfix und Suffix in zwei Durchläufen hat dieselben Kosten. Das Multiplizieren jedes Teilarrays von jedem Startpunkt aus benötigt O(n²) Zeit.

Warum benötigst du das minimale Produkt im Teilarray mit dem maximalen Produkt?

Eine negative Zahl macht aus dem negativsten Produkt, das am vorherigen Index endet, das größte. Behalte nur das größte Produkt, und dieser Kandidat ist verschwunden, wenn du ihn brauchst. In [3, -2, -4] ist das kleinste Produkt vor der -4 gleich -6, und -6 × -4 = 24 ist die Antwort.

Worin unterscheidet sich das Teilarray mit dem maximalen Produkt vom Teilarray mit der maximalen Summe?

Bei Summen ist eine negative laufende Summe immer nur nachteilig, daher reicht ein Wert pro Index aus. Bei Produkten kann ein negativer laufender Wert nach einer weiteren negativen Zahl zum besten werden, und eine Null setzt alles zurück. Deshalb führt die Produktvariante an jedem Index sowohl das größte als auch das kleinste Produkt mit.

def maxProduct(nums):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

nums = [2, -5, 3, -2, 0, 4]

Erwartete Ausgabe

Maximum Product Subarray

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Multipliziere jedes Teilarray von jedem Startpunkt aus

Von beiden Enden aus scannen und bei Nullen neu beginnen

Verfolge das größte und kleinste Produkt, das hier endet

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben