Split Array Largest Sum

Q: Qual è la complessità temporale di Split Array Largest Sum?

La ricerca binaria richiede un tempo O(n log S) , dove n è la lunghezza di nums e S la sua somma. Ogni verifica greedy consiste in un passaggio sull’array e l’intervallo dei limiti si dimezza dopo ogni verifica: circa 29 verifiche quando S = 5 × 10^8 . Usa spazio aggiuntivo O(1) . La programmazione dinamica richiede tempo O(k·n²) e spazio O(n) .

Q: Perché il controllo di fattibilità è monotono?

Se ogni parte di una suddivisione ha una somma al massimo pari a c , la stessa suddivisione ha anche ogni parte al massimo pari a c+1 . Quindi, una volta che un limite funziona, funzionano tutti i limiti più grandi; e, una volta che un limite non funziona, non funziona nessuno dei limiti più piccoli. Le risposte formano una sequenza di no seguita da una sequenza di sì, ed è proprio ciò che serve alla ricerca binaria per trovare il confine.

Q: Perché il controllo greedy trova il minor numero di parti?

Greedy continua ad aggiungere valori a una parte finché il successivo non supererebbe il limite. Confrontalo con qualsiasi suddivisione valida, parte per parte. Ogni parte greedy inizia nel punto in cui inizia la parte della suddivisione corrispondente o più avanti, quindi i suoi valori fino alla fine di quella parte costituiscono un pezzo di una parte che rientra nel limite. Nessun valore è negativo, quindi anche il pezzo rientra nel limite e greedy si estende almeno altrettanto. Greedy non resta mai indietro, quindi copre l'array in un numero di parti non superiore a quello di qualsiasi suddivisione.

Q: La ricerca binaria funziona con i numeri negativi?

No. Con valori negativi, aggiungere un valore può abbassare una somma, quindi l'algoritmo greedy potrebbe chiudere una parte troppo presto e non individuare una suddivisione valida. Anche dividere una parte può far sì che la somma di uno dei pezzi superi quella dell'intera parte, quindi avere meno di k parti non significa più che k parti siano valide. La programmazione dinamica non fa nessuna delle due ipotesi e rimane corretta, con un tempo di O(k·n²) .

DifficileRicerca binaria Programmazione dinamica

+10

Ricevi un array nums di interi non negativi e un intero k. Dividi nums in esattamente k parti, dove ogni parte è una sequenza non vuota di valori consecutivi e le parti mantengono il loro ordine. Ogni parte ha una somma e il costo di una suddivisione è la più grande di queste somme.

Restituisci il costo minimo raggiungibile con qualsiasi suddivisione in k parti.

Funzione

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

numsinteger-array: i valori non negativi, in ordine
kinteger: il numero di parti contigue in cui suddividerli
Restituisceinteger: il valore più piccolo possibile della somma della parte più grande

Vincoli

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ nums.length
Ogni parte contiene almeno un valore. Una parte i cui valori sono tutti 0 ha somma pari a 0, il che è consentito.

Esempi

Input: nums = [6, 2, 9, 4, 7, 3]k = 3
Output: 13
Spiegazione: La suddivisione [6, 2], [9, 4], [7, 3] ha somme pari a 8, 13 e 10, quindi il suo costo è 13. Nessuna suddivisione ha costo 12: impacchettando le parti da sinistra a destra con ogni somma al massimo pari a 12 si ottengono [6, 2], [9], [4, 7], [3], quattro parti mentre ne sono consentite solo tre.

Input: nums = [8, 1, 1, 1, 5]k = 2
Output: 8
Spiegazione: L’8 si trova in una parte, quindi nessuna suddivisione può costare meno di 8. [8] e [1, 1, 1, 5] sommano entrambe 8, quindi si raggiunge 8.

+20 test nascosti all’invio

Per approfondire

Ogni verifica greedy legge tutti i valori n. Con le somme prefisse, una verifica può invece trovare dove termina ogni parte tramite ricerca binaria. Quanto diventa veloce l'intero metodo quando k è piccolo e nums è lungo?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Le due esigenze sono in contrasto: devi usare esattamente k parti e vuoi che la parte più grande sia il più piccola possibile. Provare ogni posizione per i k-1 tagli diventa impraticabile, e un programma dinamico sui prefissi riduce il problema a O(k·n²), ancora troppo lento per 5000 valori. L’idea veloce capovolge la domanda. Invece di cercare la suddivisione migliore, ipotizza un limite massimo e chiediti se k parti possono restare al di sotto di esso. Una sola passata greedy risponde alla domanda; le risposte cambiano una sola volta man mano che il limite aumenta, e la ricerca binaria trova il punto di cambiamento in circa 29 passate.

Programmazione dinamica sui prefissi

Corretto, ma non termina sui test più grandi

Intuizione

Osserva l’ultima parte di una suddivisione. Se i primi j valori formano p parti, l’ultima parte è una sequenza nums[i..j-1] e i primi i valori formano le altre p-1 parti. Il costo è il maggiore tra due numeri: il costo di quelle p-1 parti e la somma dell’ultima sequenza. Qualunque sia l’ultima sequenza, vuoi suddividere i primi i valori nel modo meno costoso possibile, e questa suddivisione ottimale non dipende da nulla alla sua destra. Quindi puoi calcolarla una volta e riutilizzarla.

Indichiamo con best[p][j] il costo minimo per suddividere i primi j valori in p parti. Per una sola parte non c’è scelta: best[1][j] è la somma dei primi j valori. Per più parti, prova ogni possibile inizio i dell’ultima parte: best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), dove prefix[j] è la somma dei primi j valori. L’inizio i va da p-1, perché servono almeno p-1 valori per formare p-1 parti non vuote, fino a j-1, perché l’ultima parte deve contenere un valore. La risposta è best[k][n]. La riga p legge solo la riga p-1, quindi bastano due righe di lunghezza n+1.

Nel primo esempio, suddividere [6, 2, 9, 4] in due parti può significare terminare la prima parte dopo 6 (costo max(6, 15) = 15), dopo 2 (max(8, 13) = 13) oppure dopo 9 (max(17, 4) = 17), quindi best[2][4] = 13. Poi best[3][6] prova l’ultima parte [7, 3] e ottiene max(13, 10) = 13, valore che nessun altro punto di inizio migliora.

Il problema è il lavoro da fare. Ci sono k righe, n estremi per riga e fino a n possibili inizi per estremo: fino a k·n²/2 passaggi. Con n = 5000 e k = 2500, il ciclo interno viene eseguito circa 1.8 × 10^10 volte: 18 secondi anche a 10^9 semplici passaggi al secondo. Vale comunque la pena conoscere la programmazione dinamica: non presume mai che i valori siano non negativi, quindi continua a funzionare nei casi in cui il metodo veloce non funziona.

Algoritmo

Costruisci prefix, dove prefix[j] è la somma dei primi j valori.
Imposta la riga per una parte: best[j] = prefix[j].
Per ogni numero di parti p da 2 a k e per ogni estremo j da p a n, calcola il minimo, per i da p-1 a j-1, di max(best[i], prefix[j] - prefix[i]).
Memorizza questi minimi in una nuova riga e impostala come best.
Restituisci best[n].

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]

Ricerca binaria sulla somma più grande

Intuizione

Riformula la domanda. Scegli un limite c e chiediti: si può dividere nums in k parti in modo che la somma di ogni parte sia al massimo c? La risposta al problema è il limite minimo per cui la risposta è sì. Questa domanda è molto più semplice dell’originale, per due motivi.

Primo, basta una passata greedy per rispondere. Procedi da sinistra a destra e continua ad aggiungere valori alla parte corrente finché la sua somma resta entro c; quando il valore successivo la supererebbe, chiudi la parte e iniziane una nuova con quel valore. Questo usa il minor numero di parti possibile tra tutte le suddivisioni che rispettano il limite. Confrontala con qualsiasi altra suddivisione valida, parte per parte. Entrambe le prime parti iniziano dal primo valore e l’algoritmo greedy si ferma solo quando il valore successivo non ci sta, quindi la prima parte greedy termina almeno altrettanto a destra. La seconda parte greedy inizia quindi allo stesso punto o più avanti rispetto all’altra seconda parte. I suoi valori fino alla fine di quella parte ne sono una porzione e, poiché non ci sono valori negativi, una porzione non può avere una somma superiore all’intero, quindi ci sta e l’algoritmo greedy arriva di nuovo almeno altrettanto lontano. L’algoritmo greedy non resta mai indietro, quindi non ha mai bisogno di più parti.

Secondo, avere meno parti di k va bene tanto quanto averne esattamente k. Se l’algoritmo greedy ha bisogno di m < k parti, dividi in due una parte che contiene almeno due valori. Le sue porzioni hanno una somma non superiore a quella dell’intera parte, perché nessun valore è negativo e, poiché n ≥ k, c’è sempre una parte di questo tipo finché non arrivi a k. Quindi il test è partsNeeded(c) ≤ k.

Ora la proprietà fondamentale: il test è monotono. Se il limite c va bene, va bene anche c+1, perché la stessa suddivisione continua a rispettare un limite più grande. Per i limiti da max(nums) a sum(nums), le risposte sono no, no, ..., no, sì, sì, ..., sì, e cerchi il primo sì. L’intervallo è sicuro a entrambe le estremità: nessun limite inferiore a max(nums) può contenere quel valore e il totale ci sta sempre in una sola parte. Il primo sì è anche un costo reale, non solo un limite: se nessuna parte della sua suddivisione avesse una somma esattamente pari a c, anche il limite c-1 andrebbe bene.

Segui il primo esempio, [6, 2, 9, 4, 7, 3] con k = 3. I limiti vanno da 9 a 31. Con il limite 20 si ottengono [6, 2, 9], [4, 7, 3]: 2 parti, sì, quindi l’intervallo diventa da 9 a 20. Con il limite 14 si ottengono [6, 2], [9, 4], [7, 3]: 3 parti, sì, intervallo da 9 a 14. Con il limite 11 si ottengono [6, 2], [9], [4, 7], [3]: 4 parti, no, intervallo da 12 a 14. Con il limite 13 servono 3 parti, sì, intervallo da 12 a 13. Con il limite 12 ne servono 4, no, quindi la risposta è 13.

Ogni passata legge n valori e l’intervallo si dimezza ogni volta. Con un totale S fino a 5 × 10^8, si tratta di circa 29 passate su 5000 valori, all’incirca 150000 operazioni.

Algoritmo

Imposta lo = max(nums) e hi = sum(nums).
Mentre lo < hi, calcola mid = lo + (hi - lo) / 2.
Conta le parti che l'algoritmo greedy richiede con il limite mid: inizia con 1 parte e una somma parziale di 0; quando aggiungere un valore supererebbe mid, aggiungi una parte e reimposta la somma a quel valore.
Se il conteggio è al massimo k, imposta hi = mid; altrimenti imposta lo = mid + 1.
Restituisci lo.

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

Trappole e casi limite

La ricerca è breve, quindi i bug si trovano nel controllo greedy e nei limiti.

Iniziare con lo al di sotto di max(nums). Il controllo greedy inserisce un valore più grande del limite in una parte a sé stante e prosegue, quindi considera adeguato un limite di 5 per [1, 9] con k = 2. Inizia dal valore più grande oppure fai in modo che il controllo fallisca quando un singolo valore supera il limite.
Verificare partsNeeded(c) == k. Spesso il greedy richiede meno parti di k: per [3, 0, 4] e k = 3, con limite 4 si ottengono [3, 0], [4]. Con == nessun limite supera il controllo. Le parti in meno possono sempre essere ulteriormente suddivise, quindi verifica ≤ k.
Iniziare a contare le parti da 0. La prima parte esiste prima che un valore la faccia traboccare, quindi il conteggio inizia da 1.
Impostare hi = mid - 1 quando mid funziona. In questo modo si può saltare la risposta stessa. Mantieni hi = mid e ripeti il ciclo finché lo < hi.
Iniziare da 0 per la i della programmazione dinamica. Una cella best[i] con i < p-1 rappresenta meno valori che parti, cosa impossibile con qualsiasi suddivisione; in una riga inizializzata a zeri, viene letta come costo 0. Per [100, 1, 1] con k = 3, la programmazione dinamica restituisce quindi 2 invece di 100. Inizia da i uguale a p-1.
Overflow con limiti più alti. In questo caso il totale è al massimo 5 × 10^8, quindi gli interi a 32 bit sono sufficienti. Se i valori raggiungono 10^6, già 2148 valori superano 2^31-1, quindi usa somme a 64 bit.

Domande frequenti4

Qual è la complessità temporale di Split Array Largest Sum?

La ricerca binaria richiede un tempo O(n log S), dove n è la lunghezza di nums e S la sua somma. Ogni verifica greedy consiste in un passaggio sull’array e l’intervallo dei limiti si dimezza dopo ogni verifica: circa 29 verifiche quando S = 5 × 10^8. Usa spazio aggiuntivo O(1). La programmazione dinamica richiede tempo O(k·n²) e spazio O(n).

Perché il controllo di fattibilità è monotono?

Se ogni parte di una suddivisione ha una somma al massimo pari a c, la stessa suddivisione ha anche ogni parte al massimo pari a c+1. Quindi, una volta che un limite funziona, funzionano tutti i limiti più grandi; e, una volta che un limite non funziona, non funziona nessuno dei limiti più piccoli. Le risposte formano una sequenza di no seguita da una sequenza di sì, ed è proprio ciò che serve alla ricerca binaria per trovare il confine.

Perché il controllo greedy trova il minor numero di parti?

Greedy continua ad aggiungere valori a una parte finché il successivo non supererebbe il limite. Confrontalo con qualsiasi suddivisione valida, parte per parte. Ogni parte greedy inizia nel punto in cui inizia la parte della suddivisione corrispondente o più avanti, quindi i suoi valori fino alla fine di quella parte costituiscono un pezzo di una parte che rientra nel limite. Nessun valore è negativo, quindi anche il pezzo rientra nel limite e greedy si estende almeno altrettanto. Greedy non resta mai indietro, quindi copre l'array in un numero di parti non superiore a quello di qualsiasi suddivisione.

La ricerca binaria funziona con i numeri negativi?

No. Con valori negativi, aggiungere un valore può abbassare una somma, quindi l'algoritmo greedy potrebbe chiudere una parte troppo presto e non individuare una suddivisione valida. Anche dividere una parte può far sì che la somma di uno dei pezzi superi quella dell'intera parte, quindi avere meno di k parti non significa più che k parti siano valide. La programmazione dinamica non fa nessuna delle due ipotesi e rimane corretta, con un tempo di O(k·n²).

Python

def splitArray(nums, k):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso