Maximum Sum Subarray of Size K

Q: Che cos'è una finestra scorrevole di dimensione fissa?

È un intervallo di esattamente k elementi adiacenti che si sposta di un passo alla volta lungo un array. Invece di ricalcolare l’intervallo da zero a ogni posizione, aggiorni un valore progressivo: aggiungi l’elemento che entra da destra e rimuovi quello che esce da sinistra. In questo modo, il lavoro passa da O(n·k) a O(n) .

Q: Qual è la complessità temporale del sottovettore con somma massima di dimensione k?

Con una finestra scorrevole, il tempo è O(n) e lo spazio aggiuntivo è O(1) : una passata per sommare la prima finestra, poi un’addizione e una sottrazione per ogni passaggio. Sommare separatamente ogni finestra richiede (n-k+1) × k addizioni, ovvero O(n·k) , circa 2.5 × 10^7 per n = 10^4 e k = 5000 .

Q: In che cosa è diverso dal problema del sottarray massimo?

Qui la lunghezza è fissata a k , quindi ogni candidato è una finestra e una somma mobile le copre tutte. Nel problema del sottarray massimo, la lunghezza è libera e serve l'algoritmo di Kadane, che decide a ogni elemento se estendere la sequenza corrente o iniziarne una nuova. Una finestra fissa non offre mai questa scelta.

Q: Si può risolvere anche con le somme prefisse?

Sì. Costruisci prefix[i] come somma dei primi i elementi, e la finestra che inizia in s ha somma prefix[s+k] - prefix[s] . Anche questo richiede tempo O(n) , ma memorizza n+1 totali. La finestra scorrevole calcola le stesse somme con due variabili.

FacileFinestra scorrevole

+10

Ricevi un array di numeri interi nums e una lunghezza della finestra k. Esamina ogni sequenza di esattamente k elementi adiacenti e restituisci la somma più grande tra quelle ottenute. I valori possono essere negativi, quindi anche la risposta può essere negativa.

Funzione

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

numsinteger-array: l'array di numeri interi
kinteger: quanti elementi adiacenti contiene ciascuna finestra
Restituisceinteger: la somma più grande di k elementi consecutivi

Vincoli

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

Esempi

Input: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Output: 10
Spiegazione: Le cinque finestre di lunghezza 3 sommano 6, 9, 8, 10 e 4. La più grande è 7 + (-2) + 5 = 10.

Input: nums = [-3, -8, -1, -6]k = 2
Output: -7
Spiegazione: Tutti i valori sono negativi, quindi anche tutte le somme delle finestre lo sono: -11, -9 e -7. La più grande è -1 + (-6) = -7.

Input: nums = [5, -2, 4]k = 3
Output: 7
Spiegazione: Quando k è uguale alla lunghezza dell'array, c'è una finestra, l'intero array, e 5 + (-2) + 4 = 7.

+15 test nascosti all’invio

Per approfondire

Puoi anche restituire il punto di inizio della finestra migliore, scegliendo quella più a sinistra quando più finestre sono a pari merito?

Suggerimenti

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

0 di 3 aperti

Soluzione

Ci sono n-k+1 finestre e calcolare da zero la somma di ciascuna richiede k addizioni. Il trucco è che due finestre adiacenti si sovrappongono in tutti gli elementi tranne due. Fai scorrere la finestra invece di ricostruirla: un valore entra, uno esce e calcolare la somma di ogni finestra richiede due operazioni.

Addiziona ogni finestra

Corretto, ma non termina sui test più grandi

Intuizione

Una finestra è determinata dal punto in cui inizia. Può iniziare all'indice 0, 1 e così via fino a n-k, perché un punto di partenza successivo supererebbe la fine dell'array. Per ogni punto di partenza, somma gli elementi k e confronta il totale con il migliore ottenuto finora.

Per [4, -1, 3, 7, -2, 5, 1] e k = 3 si ottengono le somme 6, 9, 8, 10, 4, e la risposta è 10. Inizializza il valore migliore con la somma della prima finestra, oppure con il numero intero più piccolo, mai con 0: se tutti i valori sono negativi, 0 supererebbe ogni finestra reale.

Il costo è di (n-k+1) × k addizioni. Raggiunge il massimo quando k è circa la metà di n: con n = 10^4 e k = 5000 si hanno 5001 × 5000, circa 2.5 × 10^7 addizioni, e quasi tutte ripetono operazioni già eseguite per la finestra precedente.

Algoritmo

Imposta best al valore più piccolo possibile.
Per ogni inizio da 0 a n-k, imposta total = 0.
Aggiungi nums[start] fino a nums[start+k-1] a total.
Se total supera best, memorizzalo.
Restituisci best.

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

Fai scorrere una finestra fissa

Intuizione

Confronta la finestra che inizia all'indice 0 con quella che inizia all'indice 1. In [4, -1, 3, 7, -2, 5, 1] con k = 3, sono 4 + (-1) + 3 = 6 e (-1) + 3 + 7 = 9. Entrambe contengono -1 e 3. La seconda somma è la prima più il valore entrato, 7, meno il valore uscito, 4: 6 + 7 - 4 = 9.

Questo vale per ogni passaggio. Quando l'estremità destra della finestra si sposta all'indice i, l'elemento in i entra e quello in i-k esce. Quindi calcoli una volta la somma della prima finestra, poi aggiorni la somma con un'addizione e una sottrazione per ogni passaggio. Le somme sono 6, 9, 8, 10, 4, le stesse del metodo a forza bruta, e conservi la più grande.

Ogni elemento entra una volta ed esce al massimo una volta, quindi il tempo è O(n). Conservi due numeri, la somma della finestra corrente e la migliore, quindi lo spazio aggiuntivo è O(1). Qui nessuna somma supera 10^4 × 10^4 = 10^8, quindi basta un intero a 32 bit.

Algoritmo

Aggiungi nums[0] fino a nums[k-1] a window.
Imposta best = window.
Per ogni i da k a n-1, aggiungi nums[i] e sottrai nums[i-k].
Dopo ogni passaggio, imposta best al maggiore tra best e window.
Restituisci best.

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

Trappole e casi limite

L'idea della finestra è semplice, quindi i bug si nascondono nei valori iniziali e negli indici.

Inizializzare best a 0. Con [-3, -8, -1, -6] e k = 2, la risposta reale è -7, ma un valore di best pari a 0 non viene mai superato e viene restituito come risposta.
Sottrarre l'elemento sbagliato. Quando entra nums[i], l'elemento che esce è nums[i-k]. Usare nums[i-k+1] o nums[i-k-1] produce finestre della lunghezza sbagliata.
Interrompere la forza bruta un avvio troppo presto. L'ultima finestra inizia da n-k, quindi il ciclo deve includerla. Con k = n è l'unica finestra e, con un errore di uno, non viene controllata alcuna finestra e viene restituito il valore iniziale di best.
Confrontare solo dopo il ciclo. La finestra migliore può essere la prima, quindi confronta anche la prima somma oppure inizializza best con essa.
Dimenticare che R e Lua contano a partire da 1. La prima finestra è nums[1..k] e l'elemento che esce quando entra nums[i] è sempre nums[i-k].

Domande frequenti4

Che cos'è una finestra scorrevole di dimensione fissa?

È un intervallo di esattamente k elementi adiacenti che si sposta di un passo alla volta lungo un array. Invece di ricalcolare l’intervallo da zero a ogni posizione, aggiorni un valore progressivo: aggiungi l’elemento che entra da destra e rimuovi quello che esce da sinistra. In questo modo, il lavoro passa da O(n·k) a O(n).

Qual è la complessità temporale del sottovettore con somma massima di dimensione k?

Con una finestra scorrevole, il tempo è O(n) e lo spazio aggiuntivo è O(1): una passata per sommare la prima finestra, poi un’addizione e una sottrazione per ogni passaggio. Sommare separatamente ogni finestra richiede (n-k+1) × k addizioni, ovvero O(n·k), circa 2.5 × 10^7 per n = 10^4 e k = 5000.

In che cosa è diverso dal problema del sottarray massimo?

Qui la lunghezza è fissata a k, quindi ogni candidato è una finestra e una somma mobile le copre tutte. Nel problema del sottarray massimo, la lunghezza è libera e serve l'algoritmo di Kadane, che decide a ogni elemento se estendere la sequenza corrente o iniziarne una nuova. Una finestra fissa non offre mai questa scelta.

Si può risolvere anche con le somme prefisse?

Sì. Costruisci prefix[i] come somma dei primi i elementi, e la finestra che inizia in s ha somma prefix[s+k] - prefix[s]. Anche questo richiede tempo O(n), ma memorizza n+1 totali. La finestra scorrevole calcola le stesse somme con due variabili.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso