Split Array Largest Sum

Q: Wie hoch ist die Zeitkomplexität von „Split Array Largest Sum“?

Die binäre Suche benötigt O(n log S) Zeit, wobei n die Länge von nums und S ihre Summe ist. Jede gierige Prüfung durchläuft das Array einmal, und der Bereich der Obergrenzen halbiert sich nach jeder Prüfung: etwa 29 Prüfungen bei S = 5 × 10^8 . Sie benötigt zusätzlich O(1) Speicherplatz. Die DP benötigt O(k·n²) Zeit und O(n) Speicherplatz.

Q: Warum ist die Machbarkeitsprüfung monoton?

Wenn jeder Teil einer Aufteilung höchstens c ergibt, ist jeder Teil derselben Aufteilung auch höchstens c+1 . Wenn also eine Obergrenze funktioniert, funktioniert jede größere Obergrenze, und wenn eine Obergrenze scheitert, scheitert auch jede kleinere Obergrenze. Die Antworten bilden zunächst eine Folge von Nein und danach eine Folge von Ja – genau das braucht die binäre Suche, um die Grenze zu finden.

Q: Warum findet die Greedy-Prüfung die wenigsten Teile?

Der Greedy-Algorithmus fügt einer Teilmenge so lange Werte hinzu, bis der nächste Wert die Obergrenze überschreiten würde. Vergleiche ihn Teil für Teil mit einer beliebigen gültigen Aufteilung. Jeder Greedy-Teil beginnt an oder nach dem entsprechenden Teil der anderen Aufteilung, und seine Werte bis zum Ende dieses Teils sind ein Ausschnitt eines Teils, der unter der Obergrenze bleibt. Kein Wert ist negativ, also passt auch der Ausschnitt, und der Greedy-Algorithmus reicht mindestens genauso weit. Der Greedy-Algorithmus bleibt nie zurück, daher deckt er das Array mit so wenigen Teilen ab wie jede andere Aufteilung.

Q: Funktioniert die binäre Suche mit negativen Zahlen?

Nein. Bei negativen Werten kann das Addieren eines Werts eine Summe verringern, sodass der Greedy-Ansatz einen Abschnitt zu früh abschließen und eine mögliche Aufteilung verpassen kann. Das Aufteilen eines Abschnitts kann außerdem die Summe eines Teilstücks über die des Ganzen hinaus erhöhen, sodass weniger als k Abschnitte nicht mehr bedeutet, dass k Abschnitte funktionieren. Die DP trifft keine dieser Annahmen und bleibt korrekt, bei einer Laufzeit von O(k·n²) .

SchwerBinäre Suche Dynamische Programmierung

+10

Du erhältst ein Array nums aus nicht negativen Ganzzahlen und eine Ganzzahl k. Teile nums in genau k Teile auf, wobei jeder Teil aus einer nicht leeren Folge benachbarter Werte besteht und die Reihenfolge der Teile erhalten bleibt. Jeder Teil hat eine Summe, und die Kosten einer Aufteilung entsprechen der größten dieser Summen.

Gib die kleinsten Kosten zurück, die bei einer Aufteilung in k Teile erreicht werden können.

Funktion

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

numsinteger-array: die nicht negativen Werte, der Reihe nach
kinteger: die Anzahl zusammenhängender Teile, in die sie geschnitten werden sollen
Gibt zurückinteger: der kleinstmögliche Wert der größten Teilsumme

Einschränkungen

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Jeder Teil enthält mindestens einen Wert. Ein Teil, dessen Werte alle 0 sind, ergibt in der Summe 0, was zulässig ist.

Beispiele

Eingabe: nums = [6, 2, 9, 4, 7, 3]k = 3
Ausgabe: 13
Erklärung: Die Aufteilung [6, 2], [9, 4], [7, 3] hat die Summen 8, 13 und 10, daher betragen ihre Kosten 13. Keine Aufteilung kostet 12: Packt man die Teile von links nach rechts so, dass jede Summe höchstens 12 beträgt, erhält man [6, 2], [9], [4, 7], [3] – vier Teile, obwohl nur drei erlaubt sind.

Eingabe: nums = [8, 1, 1, 1, 5]k = 2
Ausgabe: 8
Erklärung: Die 8 befindet sich in einem Teil, daher kann keine Aufteilung weniger als 8 kosten. [8] und [1, 1, 1, 5] ergeben beide zusammen 8, also wird 8 erreicht.

+20 versteckte Tests beim Einreichen

Weiterführende Frage

Jede Greedy-Prüfung liest alle n-Werte. Mit Präfixsummen kann eine Prüfung stattdessen per binärer Suche ermitteln, wo jeder Teil endet. Wie schnell ist die gesamte Methode, wenn k klein und nums lang ist?

Tipps

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

0 von 3 geöffnet

Lösung

Die beiden Anforderungen stehen im Widerspruch zueinander: Du musst genau k Teile verwenden und möchtest, dass der größte Teil so klein wie möglich ist. Alle Möglichkeiten für die k-1 Trennstellen auszuprobieren, wird schnell zu aufwendig, und ein dynamisches Programm über Präfixe reduziert den Aufwand auf O(k·n²), was für 5000 Werte immer noch zu langsam ist. Die schnelle Idee dreht die Frage um. Statt nach der besten Aufteilung zu suchen, rätst du eine Obergrenze und fragst, ob k Teile darunter bleiben können. Ein gieriger Durchlauf beantwortet das; die Antworten ändern sich mit zunehmender Obergrenze nur ein einziges Mal, und die binäre Suche findet diesen Umschlagspunkt in etwa 29 Durchläufen.

Dynamische Programmierung über Präfixe

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

Idee

Betrachte den letzten Teil einer Aufteilung. Wenn die ersten j Werte p Teile bilden, ist der letzte Teil ein zusammenhängender Abschnitt nums[i..j-1], und die ersten i Werte bilden die übrigen p-1 Teile. Die Kosten sind das Maximum aus zwei Zahlen: den Kosten dieser p-1 Teile und der Summe des letzten Abschnitts. Unabhängig davon, wie der letzte Abschnitt aussieht, möchtest du die ersten i Werte so günstig wie möglich aufteilen, und diese beste Aufteilung hängt von nichts rechts davon ab. Du kannst sie also einmal berechnen und wiederverwenden.

Bezeichne mit best[p][j] die geringsten Kosten, um die ersten j Werte in p Teile aufzuteilen. Bei einem Teil gibt es keine Wahl: best[1][j] ist die Summe der ersten j Werte. Bei mehr Teilen probierst du jeden Start i des letzten Teils aus: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), wobei prefix[j] die Summe der ersten j Werte ist. Der Start i läuft von p-1, weil p-1 nicht leere Teile mindestens p-1 Werte benötigen, bis j-1, weil der letzte Teil einen Wert enthalten muss. Die Antwort ist best[k][n]. Zeile p liest nur aus Zeile p-1, daher reichen zwei Zeilen der Länge n+1 aus.

Im ersten Beispiel kann die Aufteilung von [6, 2, 9, 4] in zwei Teile nach 6 enden (Kosten max(6, 15) = 15), nach 2 (max(8, 13) = 13) oder nach 9 (max(17, 4) = 17), also ist best[2][4] = 13. Dann probiert best[3][6] den letzten Teil [7, 3] aus und erhält max(13, 10) = 13, was kein anderer Start unterbietet.

Der Aufwand ist das Problem. Es gibt k Zeilen, n Enden pro Zeile und bis zu n Starts pro Ende: bis zu k·n²/2 Schritte. Bei n = 5000 und k = 2500 wird die innere Schleife etwa 1.8 × 10^10 Mal ausgeführt: 18 Sekunden, selbst bei 10^9 einfachen Schritten pro Sekunde. Diese dynamische Programmierung ist trotzdem wissenswert: Sie setzt niemals voraus, dass die Werte nicht negativ sind, und funktioniert daher auch dort, wo die schnelle Methode nicht funktioniert.

Algorithmus

Erstelle prefix, wobei prefix[j] die Summe der ersten j Werte ist.
Setze die Zeile für einen Teil: best[j] = prefix[j].
Berechne für jede Anzahl von Teilen p von 2 bis k und jedes Ende j von p bis n das Minimum über i von p-1 bis j-1 von max(best[i], prefix[j] - prefix[i]).
Speichere diese Minima in einer neuen Zeile und mache sie zu best.
Gib best[n] zurück.

def splitArray(nums, k):
    n = len(nums)
    # prefix[j] is the sum of the first j values
    prefix = [0] * (n + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    # best[j]: the smallest largest part when the first j values form one part
    best = prefix[:]
    for parts in range(2, k + 1):
        nxt = [0] * (n + 1)
        for j in range(parts, n + 1):
            lowest = prefix[j]  # never worse than one part holding everything
            for i in range(parts - 1, j):
                # the first i values form parts-1 parts, nums[i..j-1] is the last part
                worst = max(best[i], prefix[j] - prefix[i])
                if worst < lowest:
                    lowest = worst
            nxt[j] = lowest
        best = nxt
    return best[n]

Binäre Suche nach der größten Summe

Idee

Kehre die Frage um. Wähle eine Obergrenze c und frage: Lässt sich nums in k Teile aufteilen, sodass die Summe jedes Teils höchstens c beträgt? Die Antwort auf das Problem ist die kleinste Obergrenze, für die die Antwort Ja lautet. Diese Frage ist aus zwei Gründen viel einfacher als die ursprüngliche.

Erstens lässt sie sich mit einem einzigen Greedy-Durchlauf beantworten. Gehe von links nach rechts und füge Werte zum aktuellen Teil hinzu, solange dessen Summe innerhalb von c bleibt; würde der nächste Wert sie über c hinaus erhöhen, schließe den Teil ab und beginne mit diesem Wert einen neuen. Damit erhältst du die kleinstmögliche Anzahl an Teilen, die eine Aufteilung unter dieser Obergrenze benötigt. Vergleiche sie mit jeder anderen gültigen Aufteilung, Teil für Teil. Beide ersten Teile beginnen beim ersten Wert, und der Greedy-Ansatz stoppt erst, wenn der nächste Wert nicht mehr hineinpasst. Daher reicht sein erster Teil mindestens genauso weit nach rechts. Der zweite Teil des Greedy-Ansatzes beginnt dann am selben oder an einem späteren Punkt als der zweite Teil der anderen Aufteilung. Die Werte bis zum Ende dieses Teils bilden einen Abschnitt davon, und da es keine negativen Werte gibt, ist die Summe eines Abschnitts nie größer als die des ganzen Teils. Sie passen also hinein, und der Greedy-Ansatz reicht wieder mindestens genauso weit. Der Greedy-Ansatz fällt nie zurück und benötigt daher nie mehr Teile.

Zweitens ist eine geringere Anzahl von Teilen als k genauso gut wie genau k Teile. Wenn der Greedy-Ansatz m < k Teile benötigt, teile einen Teil mit mindestens zwei Werten in zwei Teile auf. Die Summen dieser Teile sind nicht größer als die des ganzen Teils, da kein Wert negativ ist. Und da n ≥ k gilt, gibt es immer einen solchen Teil, bis du k erreichst. Der Test lautet also partsNeeded(c) ≤ k.

Nun zur entscheidenden Eigenschaft: Der Test ist monoton. Wenn die Obergrenze c funktioniert, funktioniert auch c+1, denn dieselbe Aufteilung passt weiterhin unter die größere Obergrenze. Für die Obergrenzen von max(nums) bis sum(nums) lauten die Antworten Nein, Nein, ..., Nein, Ja, Ja, ..., Ja, und gesucht ist das erste Ja. Der Bereich ist an beiden Enden sicher: Eine Obergrenze unter max(nums) kann diesen Wert nicht aufnehmen, und die Gesamtsumme passt immer in einen Teil. Das erste Ja entspricht außerdem tatsächlichen Kosten und ist nicht nur eine Schranke: Wenn die Summe keines Teils der zugehörigen Aufteilung genau c betrüge, würde auch die Obergrenze c-1 funktionieren.

Verfolge das erste Beispiel: [6, 2, 9, 4, 7, 3] mit k = 3. Die Obergrenzen reichen von 9 bis 31. Bei Obergrenze 20 ergibt sich [6, 2, 9], [4, 7, 3]: 2 Teile, Ja, der Bereich wird also auf 9 bis 20 eingegrenzt. Bei Obergrenze 14 ergibt sich [6, 2], [9, 4], [7, 3]: 3 Teile, Ja, Bereich 9 bis 14. Bei Obergrenze 11 ergibt sich [6, 2], [9], [4, 7], [3]: 4 Teile, Nein, Bereich 12 bis 14. Bei Obergrenze 13 werden 3 Teile benötigt, Ja, Bereich 12 bis 13. Bei Obergrenze 12 werden 4 Teile benötigt, Nein, also lautet die Antwort 13.

Jeder Durchlauf liest n Werte, und der Bereich halbiert sich jedes Mal. Bei einer Gesamtsumme S von bis zu 5 × 10^8 sind das etwa 29 Durchläufe über 5000 Werte, also ungefähr 150000 Schritte.

Algorithmus

Setze lo = max(nums) und hi = sum(nums).
Solange lo < hi gilt, berechne mid = lo + (hi - lo) / 2.
Zähle die Teile, die der Greedy-Ansatz bei einer Obergrenze von mid benötigt: Beginne mit 1 Teil und einer laufenden Summe von 0; wenn das Hinzufügen eines Werts mid überschreiten würde, füge einen Teil hinzu und setze die Summe mit diesem Wert neu an.
Ist die Anzahl höchstens k, setze hi = mid; andernfalls setze lo = mid + 1.
Gib lo zurück.

def splitArray(nums, k):
    def parts_needed(cap):
        # Fill each part left to right and start a new one only when the next value would pass cap.
        parts, current = 1, 0
        for x in nums:
            if current + x > cap:
                parts += 1
                current = x
            else:
                current += x
        return parts

    lo, hi = max(nums), sum(nums)  # one value per part at best, everything in one part at worst
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid needs more than k parts, so the answer is larger
    return lo

Stolperfallen und Grenzfälle

Die Suche ist kurz, daher stecken die Fehler in der Greedy-Prüfung und in den Grenzen.

lo unter max(nums) starten. Die Greedy-Prüfung packt einen Wert, der größer als die Grenze ist, in einen eigenen Abschnitt und macht weiter. Dadurch meldet sie eine Grenze von 5 für [1, 9] mit k = 2 fälschlich als zulässig. Beginne beim größten Wert oder lasse die Prüfung fehlschlagen, wenn ein einzelner Wert die Grenze überschreitet.
partsNeeded(c) == k prüfen. Greedy benötigt oft weniger als k Abschnitte: Für [3, 0, 4] und k = 3 packt die Grenze 4 die Werte in [3, 0], [4]. Mit == ist keine Grenze jemals zulässig. Weniger Abschnitte lassen sich immer weiter aufteilen, also prüfe ≤ k.
Die Abschnitte ab 0 zählen. Der erste Abschnitt existiert, bevor ein Wert ihn überlaufen lässt, daher beginnt die Zählung bei 1.
hi = mid - 1 setzen, wenn mid funktioniert. Dadurch kann die Antwort selbst übersprungen werden. Behalte hi = mid bei und wiederhole die Schleife, solange lo < hi gilt.
Das i der DP bei 0 beginnen lassen. Eine Zelle best[i] mit i < p-1 steht für weniger Werte als Abschnitte, was durch keine Aufteilung möglich ist, und in einer mit Nullen gefüllten Zeile wird sie als Kosten 0 gelesen. Für [100, 1, 1] mit k = 3 meldet die DP dann 2 statt 100. Beginne i bei p-1.
Überlauf bei größeren Grenzwerten. Hier beträgt die Summe höchstens 5 × 10^8, daher reichen 32-Bit-Ganzzahlen dafür aus. Wenn die Werte 10^6 erreichen, überschreiten bereits 2148 davon 2^31-1, also verwende 64-Bit-Summen.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Split Array Largest Sum“?

Die binäre Suche benötigt O(n log S) Zeit, wobei n die Länge von nums und S ihre Summe ist. Jede gierige Prüfung durchläuft das Array einmal, und der Bereich der Obergrenzen halbiert sich nach jeder Prüfung: etwa 29 Prüfungen bei S = 5 × 10^8. Sie benötigt zusätzlich O(1) Speicherplatz. Die DP benötigt O(k·n²) Zeit und O(n) Speicherplatz.

Warum ist die Machbarkeitsprüfung monoton?

Wenn jeder Teil einer Aufteilung höchstens c ergibt, ist jeder Teil derselben Aufteilung auch höchstens c+1. Wenn also eine Obergrenze funktioniert, funktioniert jede größere Obergrenze, und wenn eine Obergrenze scheitert, scheitert auch jede kleinere Obergrenze. Die Antworten bilden zunächst eine Folge von Nein und danach eine Folge von Ja – genau das braucht die binäre Suche, um die Grenze zu finden.

Warum findet die Greedy-Prüfung die wenigsten Teile?

Der Greedy-Algorithmus fügt einer Teilmenge so lange Werte hinzu, bis der nächste Wert die Obergrenze überschreiten würde. Vergleiche ihn Teil für Teil mit einer beliebigen gültigen Aufteilung. Jeder Greedy-Teil beginnt an oder nach dem entsprechenden Teil der anderen Aufteilung, und seine Werte bis zum Ende dieses Teils sind ein Ausschnitt eines Teils, der unter der Obergrenze bleibt. Kein Wert ist negativ, also passt auch der Ausschnitt, und der Greedy-Algorithmus reicht mindestens genauso weit. Der Greedy-Algorithmus bleibt nie zurück, daher deckt er das Array mit so wenigen Teilen ab wie jede andere Aufteilung.

Funktioniert die binäre Suche mit negativen Zahlen?

Nein. Bei negativen Werten kann das Addieren eines Werts eine Summe verringern, sodass der Greedy-Ansatz einen Abschnitt zu früh abschließen und eine mögliche Aufteilung verpassen kann. Das Aufteilen eines Abschnitts kann außerdem die Summe eines Teilstücks über die des Ganzen hinaus erhöhen, sodass weniger als k Abschnitte nicht mehr bedeutet, dass k Abschnitte funktionieren. Die DP trifft keine dieser Annahmen und bleibt korrekt, bei einer Laufzeit von O(k·n²).

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [6, 2, 9, 4, 7, 3]
k = 3

Erwartet