Split Array Largest Sum

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

O(n log S) Zeit und O(1) zusätzlicher Speicherplatz, wobei S die Summe von nums ist: Jede gierige Prüfung ist ein Durchlauf, und der Bereich der Obergrenzen halbiert sich nach jeder Prüfung. Das sind etwa 29 Prüfungen, wenn S = 5 × 10^8 . Die DP benötigt O(k·n²) Zeit.

Q: Warum ist die Machbarkeitsprüfung monoton?

Wenn jeder Teil einer Aufteilung höchstens c ergibt, passt dieselbe Aufteilung auch unter c+1 . Sobald also eine Obergrenze funktioniert, funktioniert jede größere Obergrenze, und die Antworten bestehen aus einer Folge von Nein, gefolgt von einer Folge von Ja. Die binäre Suche findet das erste Ja.

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

Nein. Ein negativer Wert kann eine Summe verringern, sodass der Greedy-Ansatz einen Teil zu früh abschließen kann, und durch das Aufteilen eines Teils kann ein Stück größer werden als das Ganze. Die DP trifft keine dieser Annahmen und bleibt korrekt.

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 ein nicht leerer zusammenhängender Abschnitt ist und die Teile ihre Reihenfolge beibehalten. 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 zerschnitten 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] kostet 13. Keine Aufteilung kostet 12: Wenn die Teile von links nach rechts unter 12 gepackt werden, ergibt das [6, 2], [9], [4, 7], [3], vier Teile.

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.

Weiterführende Frage

Mit Präfixsummen kann eine Greedy-Prüfung per binärer Suche ermitteln, wo jeder Teil endet. Wie schnell wird das gesamte Verfahren, wenn k klein ist?

Tipps

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

0 von 3 geöffnet

Lösung

Die direkte Suche nach der besten Aufteilung kostet selbst mit dynamischer Programmierung O(k·n²). Drehen wir die Frage um: Können k Teile unter einer gegebenen Obergrenze bleiben? Ein gieriger Durchlauf beantwortet diese Frage. Mit wachsender Obergrenze wechselt die Antwort genau einmal von Nein zu Ja, und die binäre Suche findet diesen Wechsel.

Dynamische Programmierung über Präfixe

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

Idee

Schreibe best[p][j] für die minimalen Kosten, die ersten j Werte in p Teile aufzuteilen. Wenn der letzte Teil nums[i..j-1] ist, entsprechen die Kosten dem größeren Wert von best[p-1][i] und der Summe dieses Teils, und die beste Aufteilung der ersten i Werte hängt von nichts rechts davon ab. Also gilt best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), wobei i von p-1 bis j-1 läuft, damit jeder Teil einen Wert enthält. Zeile p liest nur Zeile p-1, daher genügen zwei Zeilen.

Es werden bis zu k·n²/2 Schritte ausgeführt: etwa 1.8 × 10^10 für n = 5000 und k = 2500.

Algorithmus

Erstelle prefix, wobei prefix[j] die Summe der ersten j Werte ist, und setze für einen Teil best[j] = prefix[j].
Für jede Teilanzahl p von 2 bis k und jedes Ende j von p bis n nimm 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

Um eine Obergrenze c zu testen, gehst du von links nach rechts und fügst Werte zum aktuellen Teil hinzu, solange seine Summe innerhalb von c bleibt. Dann beginnst du einen neuen Teil. So erhältst du die kleinstmögliche Anzahl an Teilen. Im Vergleich zu jeder gültigen Aufteilung endet der erste Teil der Greedy-Strategie mindestens genauso weit rechts, sodass ihr nächster Teil an derselben oder einer späteren Stelle beginnt. Die Werte bis zum Ende dieses Teils bilden einen Teil eines Abschnitts, der hineinpasst. Da es keine negativen Werte gibt, ist die Summe eines Teilabschnitts nie größer als die des gesamten Abschnitts. Die Greedy-Strategie fällt also nie zurück.

Weniger als k Teile sind genauso gut wie k: Wenn du einen Teil mit zwei oder mehr Werten in zwei Teile aufteilst, erhöht sich keine der Summen. Der Test lautet also partsNeeded(c) ≤ k.

Führe eine binäre Suche nach der kleinsten Obergrenze durch, bei der der Test erfolgreich ist. Die Suche erfolgt zwischen max(nums), da dieser Wert in irgendeinem Teil liegt, und sum(nums), das immer in einen einzigen Teil passt.

Algorithmus

Setze lo = max(nums) und hi = sum(nums).
Solange lo < hi gilt, setze mid = lo + (hi - lo) / 2.
Zähle die gierigen Teilbereiche unter mid: Beginne mit 1 Teilbereich und einer Summe von 0; wenn das Hinzufügen eines Werts mid überschreiten würde, füge einen Teilbereich hinzu und setze die Summe auf diesen Wert zurück.
Wenn die Anzahl höchstens k beträgt, 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

lo unterhalb von max(nums) initialisieren. Beim Greedy-Verfahren kommt ein Wert, der größer als die Obergrenze ist, in einen eigenen Teil. Daher meldet es die Obergrenze 5 für [1, 9] mit k = 2 fälschlicherweise als passend.
partsNeeded(c) == k testen. Für [3, 0, 4] und k = 3 packt die Obergrenze 4 die Werte in [3, 0] und [4], sodass keine Obergrenze jemals passt.
Teile ab 0 zählen, wodurch jede Anzahl um eins zu klein ist.
hi = mid - 1 setzen, wenn mid funktioniert. Dadurch geht die Antwort verloren, wenn sie mid ist.
Das i der DP bei 0 beginnen lassen. Eine Zelle mit weniger Werten als Teilen wird als Kostenwert 0 gelesen, und für [100, 1, 1] mit k = 3 wird 2 statt 100 ausgegeben.

Häufige Fragen3

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

O(n log S) Zeit und O(1) zusätzlicher Speicherplatz, wobei S die Summe von nums ist: Jede gierige Prüfung ist ein Durchlauf, und der Bereich der Obergrenzen halbiert sich nach jeder Prüfung. Das sind etwa 29 Prüfungen, wenn S = 5 × 10^8. Die DP benötigt O(k·n²) Zeit.

Warum ist die Machbarkeitsprüfung monoton?

Wenn jeder Teil einer Aufteilung höchstens c ergibt, passt dieselbe Aufteilung auch unter c+1. Sobald also eine Obergrenze funktioniert, funktioniert jede größere Obergrenze, und die Antworten bestehen aus einer Folge von Nein, gefolgt von einer Folge von Ja. Die binäre Suche findet das erste Ja.

Funktioniert die binäre Suche mit negativen Zahlen?

Nein. Ein negativer Wert kann eine Summe verringern, sodass der Greedy-Ansatz einen Teil zu früh abschließen kann, und durch das Aufteilen eines Teils kann ein Stück größer werden als das Ganze. Die DP trifft keine dieser Annahmen und bleibt korrekt.

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

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe