Split Array Largest Sum

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

Tempo O(n log S) e spazio aggiuntivo O(1) , dove S è la somma di nums : ogni verifica greedy richiede un passaggio e l'intervallo dei limiti si dimezza dopo ogni verifica. Sono circa 29 verifiche quando S = 5 × 10^8 . La DP richiede tempo O(k·n²) .

Q: Perché la verifica di fattibilità è monotona?

Se ogni parte di una divisione ha una somma al massimo pari a c , la stessa divisione rientra nel limite di c+1 . Quindi, una volta che un limite funziona, funzionano anche tutti i limiti maggiori, e le risposte formano una sequenza di no seguita da una sequenza di sì. La ricerca binaria trova il primo sì.

Q: La ricerca binaria funziona con i numeri negativi?

No. Un valore negativo può ridurre una somma, quindi l'algoritmo greedy potrebbe chiudere una parte troppo presto, e dividere una parte può portare un pezzo a superare il totale. La programmazione dinamica non fa nessuna delle due ipotesi e rimane corretta.

DifficileRicerca binaria Programmazione dinamica

+10

Ti viene fornito un array nums di interi non negativi e un intero k. Dividi nums esattamente in k parti, dove ogni parte è una sequenza non vuota di valori adiacenti 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 che è possibile ottenere con una 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 tagliarli
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] costa 13. Nessuna suddivisione costa 12: impacchettando le parti da sinistra a destra entro 12 si ottengono [6, 2], [9], [4, 7], [3], quattro parti.

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] hanno entrambe somma 8.

Per approfondire

Con le somme prefisse, un controllo greedy può trovare dove termina ogni parte tramite ricerca binaria. Quanto diventa veloce l’intero metodo quando k è piccolo?

Suggerimenti

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

0 di 3 aperti

Soluzione

Cercare direttamente la migliore suddivisione costa O(k·n²) anche con la programmazione dinamica. Ribalta la domanda: le k parti possono restare entro un limite dato? Una sola passata greedy risponde, la risposta passa da no a sì una volta sola man mano che il limite cresce, e la ricerca binaria trova il punto di passaggio.

Programmazione dinamica sui prefissi

Corretto, ma non termina sui test più grandi

Intuizione

Indica con best[p][j] il costo minimo per suddividere i primi j valori in p parti. Se l’ultima parte è nums[i..j-1], il costo è il maggiore tra best[p-1][i] e la somma di quella parte, e la suddivisione migliore dei primi i valori non dipende da ciò che si trova alla sua destra. Quindi best[p][j] = min over i of max(best[p-1][i], prefix[j] - prefix[i]), con i compreso tra p-1 e j-1, in modo che ogni parte contenga un valore. La riga p legge solo la riga p-1, quindi bastano due righe.

Richiede fino a k·n²/2 passaggi: circa 1.8 × 10^10 per n = 5000 e k = 2500.

Algoritmo

Costruisci prefix, dove prefix[j] è la somma dei primi j valori, e imposta best[j] = prefix[j] per una parte.
Per ogni numero di parti p da 2 a k, e per ogni fine 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 quei minimi in una nuova riga e rendila 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

Per verificare un limite c, procedi da sinistra a destra e aggiungi valori alla parte corrente finché la loro somma non supera c, poi inizia una nuova parte. In questo modo si usano il minor numero di parti possibile. Rispetto a qualsiasi suddivisione valida, la prima parte dell’algoritmo greedy termina almeno altrettanto a destra, quindi la parte successiva inizia nello stesso punto o più avanti rispetto a quella dell’altra suddivisione. I suoi valori fino alla fine di quella parte formano un sottoinsieme di una parte la cui somma rientra nel limite e, in assenza di valori negativi, la somma di un sottoinsieme non supera mai quella dell’intera parte. Quindi l’algoritmo greedy non resta mai indietro.

Meno di k parti è altrettanto valido di k: dividere in due una parte con due o più valori non aumenta mai una somma. Quindi il test è partsNeeded(c) ≤ k.

Esegui una ricerca binaria sul limite minimo che supera il test, tra max(nums), poiché quel valore si trova in una delle parti, e sum(nums), che rientra sempre in un’unica parte.

Algoritmo

Imposta lo = max(nums) e hi = sum(nums).
Mentre lo < hi, calcola mid = lo + (hi - lo) / 2.
Conta le parti create in modo greedy con limite mid: parti da 1 parte con somma 0; quando aggiungere un valore supererebbe mid, aggiungi una parte e riavvia la somma con 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

Iniziare lo con un valore inferiore a max(nums). L’algoritmo greedy mette un valore più grande del limite in una parte a sé, quindi segnala che il limite 5 va bene per [1, 9] con k = 2.
Verificare partsNeeded(c) == k. Per [3, 0, 4] e k = 3, il limite 4 suddivide i valori in [3, 0], [4], quindi nessun limite supera mai il controllo.
Contare le parti partendo da 0, il che rende ogni conteggio inferiore di uno.
Impostare hi = mid - 1 quando mid funziona: così si perde la risposta quando è mid.
Iniziare la i della programmazione dinamica da 0. Una cella con meno valori che parti viene letta come costo 0 e [100, 1, 1] con k = 3 restituisce 2 invece di 100.

Domande frequenti3

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

Tempo O(n log S) e spazio aggiuntivo O(1), dove S è la somma di nums: ogni verifica greedy richiede un passaggio e l'intervallo dei limiti si dimezza dopo ogni verifica. Sono circa 29 verifiche quando S = 5 × 10^8. La DP richiede tempo O(k·n²).

Perché la verifica di fattibilità è monotona?

Se ogni parte di una divisione ha una somma al massimo pari a c, la stessa divisione rientra nel limite di c+1. Quindi, una volta che un limite funziona, funzionano anche tutti i limiti maggiori, e le risposte formano una sequenza di no seguita da una sequenza di sì. La ricerca binaria trova il primo sì.

La ricerca binaria funziona con i numeri negativi?

No. Un valore negativo può ridurre una somma, quindi l'algoritmo greedy potrebbe chiudere una parte troppo presto, e dividere una parte può portare un pezzo a superare il totale. La programmazione dinamica non fa nessuna delle due ipotesi e rimane corretta.

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

Test #1

Test #2

Test #3

Argomenti

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

Output atteso