Maximum Sum Subarray of Size K

Q: Was ist ein Fenster fester Größe?

Es ist ein Bereich aus genau k benachbarten Elementen, der sich Schritt für Schritt über ein Array bewegt. Statt den Bereich an jeder Position von Grund auf neu zu berechnen, aktualisierst du einen laufenden Wert: Addiere das Element, das rechts hinzukommt, und entferne das Element, das links wegfällt. Dadurch wird der Aufwand von O(n·k) auf O(n) reduziert.

Q: Wie hoch ist die Zeitkomplexität des Teilarrays der Größe k mit der maximalen Summe?

Mit einem gleitenden Fenster beträgt der Zeitaufwand O(n) und der zusätzliche Speicherplatz O(1) : ein Durchlauf, um die Summe des ersten Fensters zu berechnen, danach pro Schritt eine Addition und eine Subtraktion. Jedes Fenster separat zu summieren kostet (n-k+1) × k Additionen, also O(n·k) , bei n = 10^4 und k = 5000 etwa 2.5 × 10^7 .

Q: Worin unterscheidet sich das vom Maximum-Subarray-Problem?

Hier ist die Länge auf k festgelegt, daher ist jeder Kandidat ein Fenster, und eine gleitende Summe erfasst sie alle. Beim Problem des maximalen Teilarrays ist die Länge frei wählbar, und du benötigst Kadane's Algorithmus, der bei jedem Element entscheidet, ob der aktuelle Abschnitt verlängert oder ein neuer begonnen werden soll. Bei einem festen Fenster hast du diese Wahl nie.

Q: Kann man das auch mit Präfixsummen lösen?

Ja. Erstelle prefix[i] als Summe der ersten i Elemente, und das Fenster, das bei s beginnt, ergibt die Summe prefix[s+k] - prefix[s] . Das benötigt ebenfalls O(n) Zeit, speichert aber n+1 Summen. Mit dem gleitenden Fenster erhältst du dieselben Summen mit zwei Variablen.

LeichtSliding Window

+10

Du erhältst ein Array aus Ganzzahlen nums und eine Fensterlänge k. Betrachte jede Folge von genau k benachbarten Elementen und gib die größte Summe darunter zurück. Die Werte können negativ sein, daher kann auch die Antwort negativ sein.

Funktion

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: das Array aus Ganzzahlen
kinteger: wie viele benachbarte Elemente jedes Fenster enthält
Gibt zurückinteger: die größte Summe von k aufeinanderfolgenden Elementen

Einschränkungen

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Beispiele

Eingabe: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Ausgabe: 10
Erklärung: Die fünf Fenster der Länge 3 ergeben zusammen 6, 9, 8, 10 und 4. Das größte ist 7 + (-2) + 5 = 10.

Eingabe: nums = [-3, -8, -1, -6]k = 2
Ausgabe: -7
Erklärung: Jeder Wert ist negativ, also ist auch jede Fenstersumme negativ: -11, -9 und -7. Die größte davon ist -1 + (-6) = -7.

Eingabe: nums = [5, -2, 4]k = 3
Ausgabe: 7
Erklärung: Wenn k der Länge des Arrays entspricht, gibt es ein Fenster: das ganze Array, und 5 + (-2) + 4 = 7.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch zurückgeben, wo das beste Fenster beginnt, und bei Gleichstand das am weitesten links liegende auswählen?

Tipps

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

0 von 3 geöffnet

Lösung

Es gibt n-k+1 Fenster, und jedes von Grund auf zu summieren, erfordert k Additionen. Der Trick besteht darin, dass sich zwei benachbarte Fenster bis auf zwei Elemente überschneiden. Verschiebe das Fenster, statt es neu aufzubauen: Ein Wert kommt hinzu, ein Wert fällt weg, und jede Fenstersumme erfordert zwei Operationen.

Alle Fenster addieren

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

Idee

Ein Fenster wird dadurch festgelegt, wo es beginnt. Es kann am Index 0, 1 und so weiter bis n-k beginnen, da ein späterer Start über das Ende des Arrays hinausgehen würde. Addiere für jeden Start die k Elemente und vergleiche die Summe mit dem bisher besten Wert.

Für [4, -1, 3, 7, -2, 5, 1] und k = 3 ergeben sich die Summen 6, 9, 8, 10, 4, und die Antwort ist 10. Setze den besten Wert auf die Summe des ersten Fensters oder auf die kleinste ganze Zahl, niemals auf 0: Wenn alle Werte negativ sind, wäre 0 größer als jedes tatsächliche Fenster.

Der Aufwand beträgt (n-k+1) × k Additionen. Er ist am größten, wenn k etwa der Hälfte von n entspricht: Bei n = 10^4 und k = 5000 sind das 5001 × 5000, also etwa 2.5 × 10^7 Additionen, von denen fast alle Arbeit wiederholen, die bereits für das vorherige Fenster erledigt wurde.

Algorithmus

Setze best auf den kleinstmöglichen Wert.
Setze für jeden Startwert von 0 bis n-k total = 0.
Addiere nums[start] bis nums[start+k-1] zu total.
Wenn total größer als best ist, speichere es.
Gib best zurück.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Ein festes Fenster verschieben

Idee

Vergleiche das Fenster, das bei Index 0 beginnt, mit dem, das bei Index 1 beginnt. In [4, -1, 3, 7, -2, 5, 1] mit k = 3 sind das 4 + (-1) + 3 = 6 und (-1) + 3 + 7 = 9. Beide enthalten -1 und 3. Die zweite Summe ist die erste plus dem hinzugekommenen Wert 7 minus dem herausgefallenen Wert 4: 6 + 7 - 4 = 9.

Das gilt für jeden Schritt. Wenn sich das rechte Ende des Fensters zu Index i bewegt, kommt das Element bei i hinzu und das Element bei i-k fällt heraus. Du berechnest also zuerst einmal die Summe des ersten Fensters und aktualisierst dann die Summe bei jedem Schritt mit einer Addition und einer Subtraktion. Die Summen lauten 6, 9, 8, 10, 4, genau wie bei der Brute-Force-Methode, und du behältst den größten Wert.

Jedes Element kommt einmal hinzu und fällt höchstens einmal heraus, daher beträgt die Laufzeit O(n). Du speicherst zwei Zahlen, die aktuelle Fenstersumme und die beste Summe, daher beträgt der zusätzliche Speicherplatz O(1). Keine Summe hier überschreitet 10^4 × 10^4 = 10^8, daher reicht eine 32-Bit-Ganzzahl aus.

Algorithmus

Addiere nums[0] bis nums[k-1] zu window.
Setze best = window.
Addiere für jedes i von k bis n-1 nums[i] und ziehe nums[i-k] ab.
Setze nach jedem Schritt best auf den größeren Wert von best und window.
Gib best zurück.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Stolperfallen und Grenzfälle

Die Idee mit dem Fenster ist einfach, daher verstecken sich die Fehler in den Startwerten und den Indizes.

best mit 0 zu initialisieren. Bei [-3, -8, -1, -6] und k = 2 ist die tatsächliche Antwort -7, aber ein best von 0 wird nie übertroffen und als Antwort zurückgegeben.
Das falsche Element abzuziehen. Wenn nums[i] hinzukommt, ist das Element, das das Fenster verlässt, nums[i-k]. Mit nums[i-k+1] oder nums[i-k-1] erhältst du Fenster mit der falschen Länge.
Die Brute-Force-Suche einen Start zu früh zu beenden. Das letzte Fenster beginnt bei n-k, daher muss die Schleife diesen Wert einschließen. Bei k = n ist das das einzige Fenster; ein Off-by-one-Fehler prüft kein Fenster und gibt den Startwert von best zurück.
Erst nach der Schleife zu vergleichen. Das beste Fenster kann das erste sein, also vergleiche auch die erste Summe oder initialisiere best mit ihr.
Zu vergessen, dass R und Lua ab 1 zählen. Das erste Fenster ist nums[1..k], und das Element, das das Fenster verlässt, wenn nums[i] hinzukommt, ist weiterhin nums[i-k].

Häufige Fragen4

Was ist ein Fenster fester Größe?

Es ist ein Bereich aus genau k benachbarten Elementen, der sich Schritt für Schritt über ein Array bewegt. Statt den Bereich an jeder Position von Grund auf neu zu berechnen, aktualisierst du einen laufenden Wert: Addiere das Element, das rechts hinzukommt, und entferne das Element, das links wegfällt. Dadurch wird der Aufwand von O(n·k) auf O(n) reduziert.

Wie hoch ist die Zeitkomplexität des Teilarrays der Größe k mit der maximalen Summe?

Mit einem gleitenden Fenster beträgt der Zeitaufwand O(n) und der zusätzliche Speicherplatz O(1): ein Durchlauf, um die Summe des ersten Fensters zu berechnen, danach pro Schritt eine Addition und eine Subtraktion. Jedes Fenster separat zu summieren kostet (n-k+1) × k Additionen, also O(n·k), bei n = 10^4 und k = 5000 etwa 2.5 × 10^7.

Worin unterscheidet sich das vom Maximum-Subarray-Problem?

Hier ist die Länge auf k festgelegt, daher ist jeder Kandidat ein Fenster, und eine gleitende Summe erfasst sie alle. Beim Problem des maximalen Teilarrays ist die Länge frei wählbar, und du benötigst Kadane's Algorithmus, der bei jedem Element entscheidet, ob der aktuelle Abschnitt verlängert oder ein neuer begonnen werden soll. Bei einem festen Fenster hast du diese Wahl nie.

Kann man das auch mit Präfixsummen lösen?

Ja. Erstelle prefix[i] als Summe der ersten i Elemente, und das Fenster, das bei s beginnt, ergibt die Summe prefix[s+k] - prefix[s]. Das benötigt ebenfalls O(n) Zeit, speichert aber n+1 Summen. Mit dem gleitenden Fenster erhältst du dieselben Summen mit zwei Variablen.

Python

def maxSumSubarray(nums, k):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Erwartet