Maximales Teilarray und Teilarray mit maximalem Produkt

Beim Problem Maximum Subarray sollen Sie das zusammenhängende Teilarray innerhalb eines eindimensionalen Zahlenarrays finden, dessen Summe am größten ist. Im Beispiel [-2, 1, -3, 4, -1, 2, 1, -5, 4] ergibt das Teilarray [4, -1, 2, 1] die maximale Summe 6. Ein Brute-Force-Ansatz mit O(n²) prüft alle Teilarrays, aber der Kadane-Algorithmus löst das Problem in O(n).

Der Kadane-Algorithmus durchläuft das Array einmal und verwaltet dabei eine laufende Summe current_sum. Bei jedem Element entscheiden Sie: Ist es besser, das bestehende Teilarray zu erweitern oder mit diesem Element neu zu beginnen? Wenn current_sum negativ wird, würde es jedes zukünftige Teilarray nur verschlechtern, daher beginnen Sie neu. Die Rekurrenz lautet current_sum = max(num, current_sum + num).

Verfolgen wir den Kadane-Algorithmus für [-2, 1, -3, 4, -1, 2, 1, -5, 4]: Wir beginnen mit curr=-2, max=-2. Bei 1: curr=max(1,-2+1)=1, max=1. Bei -3: curr=max(-3,1-3)=-2, max=1. Bei 4: curr=max(4,-2+4)=4, max=4. Bei -1: curr=3, max=4. Bei 2: curr=5, max=5. Bei 1: curr=6, max=6. Bei -5: curr=1. Bei 4: curr=5, max=6. Der Algorithmus identifiziert korrekt das bei Index 6 endende Teilarray als optimale Lösung.

Wenn der Interviewer Sie auffordert, das Teilarray selbst zurückzugeben (nicht nur die Summe), müssen Sie Start- und Endindizes verfolgen. Wenn Sie neu beginnen (weil num > current_sum + num), aktualisieren Sie einen temp_start. Wenn Sie max_sum aktualisieren, speichern Sie temp_start als start und den aktuellen Index als end. Dies fügt demselben O(n)-Algorithmus einen O(1)-Zusatzaufwand hinzu.

Das Problem Maximum Product Subarray ist aufgrund von negativen Zahlen schwieriger als die Summenvariante. Zwei negative Zahlen ergeben beim Multiplizieren eine positive Zahl, sodass ein sehr negatives Produkt nach der Multiplikation mit einer weiteren negativen Zahl zum Maximum werden kann. Für [2, 3, -2, 4] lautet die Lösung 6 ([2, 3]). Für [-2, 0, -1] lautet die Lösung 0. Wir müssen bei jedem Schritt sowohl die maximalen als auch die minimalen Produkte verfolgen.

Die entscheidende Erkenntnis lautet: An jeder Position ist das aktuelle maximale Produkt eines von num, max_so_far * num oder min_so_far * num (letzteres ist hilfreich, wenn eine negative Zahl das Minimum in ein Maximum umwandelt). Entsprechend gilt dasselbe für das Minimum. Aktualisieren Sie beide Werte cur_max und cur_min gleichzeitig anhand der vorherigen Werte, damit Sie innerhalb desselben Schritts nicht bereits aktualisierte Werte verwenden.

Betrachten Sie [-3, -10, 5]. Nach der Verarbeitung von -3: max=-3, min=-3. Nach -10: Die Kandidaten sind (-10, 30, 30) → max=30, min=-10. Nach 5: Die Kandidaten sind (5, 150, -50) → max=150. Ohne die Verfolgung von min_prod würden Sie den Vorzeichenwechsel übersehen, der auftritt, wenn ein stark negatives Minimum mit einer weiteren negativen Zahl multipliziert wird. Berechnen Sie max und min immer aus denselben vorherigen Werten, um einen Fehler durch das Lesen veralteter Werte zu vermeiden.

Eine Null im Array setzt beide laufenden Produkte auf null zurück und teilt das Array damit effektiv in unabhängige Teilarrays. Wenn num = 0 gilt, sind sowohl max_prod * 0 = 0 als auch min_prod * 0 = 0 gleich 0. Somit werden alle drei Kandidaten zu 0, und das bisherige Maximum bleibt erhalten. Es ist kein Sonderfallcode erforderlich — die allgemeine Formel verarbeitet Nullen ganz natürlich.

Ein alternativer Ansatz durchläuft das Array von links nach rechts und von rechts nach links und setzt das laufende Produkt bei einer Null auf 1 zurück. Das Teilarray mit dem maximalen Produkt überschreitet niemals eine Null. Wenn eine negative Zahl die Situation in eine Richtung verschlechtert, erkennt der umgekehrte Durchlauf den Vorzeichenwechsel. Dieser Ansatz ist elegant, aber die Methode zur Verfolgung von min/max wird in Interviews häufiger erwartet.

Summen- und Produkt-Teilarrays unterscheiden sich in wichtigen Punkten. Bei Summen sind negative Zahlen immer schädlich, daher beginnen Sie nach dem Greedy-Prinzip neu. Bei Produkten sind zwei negative Zahlen hilfreich, deshalb müssen Sie beide Extreme verfolgen. Außerdem sind Nullen für Produkte ein Abbruchpunkt, während sie für Summen nur mäßig schädlich sind. Weisen Sie im Interview ausdrücklich auf diese Unterschiede hin und erklären Sie, warum die Verfolgung des Minimums erforderlich ist, bevor Sie Code schreiben.

Sowohl der Kadane-Algorithmus (maximale Summe) als auch die Min-/Max-Verfolgung (maximales Produkt) benötigen O(n) Zeit und O(1) Speicher. Wichtige Tipps für Interviews: (1) Erwähnen Sie bei der maximalen Summe die Divide-and-Conquer-Alternative mit O(n log n), um Ihre Kenntnisse zu zeigen. (2) Betonen Sie beim maximalen Produkt, dass Sie min_prod und max_prod gleichzeitig anhand der vorherigen Werte aktualisieren, damit Sie keine veralteten Daten verwenden. (3) Klären Sie immer: Darf das Array leer sein? Muss das Teilarray nicht leer sein? (Ja, es muss konventionsgemäß nicht leer sein.)

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

In dieser Lektion haben Sie Folgendes gelernt: Der Kadane-Algorithmus löst das Problem des Teilarrays mit maximaler Summe in O(n), indem er bei jedem Element zwischen Erweitern und Neustart wählt, für das Teilarray mit maximalem Produkt müssen aufgrund der Vorzeichenwechsel bei negativen Zahlen sowohl die minimalen als auch die maximalen laufenden Produkte verfolgt werden und Nullen setzen das laufende Produkt ohne Sonderfallcode auf natürliche Weise zurück. Als Nächstes untersuchen wir das Word-Break-Problem mithilfe einer eindimensionalen DP-Tabelle.