Il sottoarray di somma massima con l'algoritmo di Kadane
In questa lezione userai l'algoritmo di Kadane per trovare il tratto continuo con la somma massima in una sola passata sulla lista.
Introduzione
Il problema
Qual è stato il periodo migliore per un titolo in borsa, il tratto di stagione con più punti, la parte più redditizia di un viaggio? Sono tutte domande sul sottoarray massimo. Controllare tutti i possibili inizi e fini è lento. L'algoritmo di Kadane risolve il problema in un solo passaggio.
Immaginalo così
L'algoritmo di Kadane è come camminare lungo un sentiero raccogliendo oro e pagando pedaggi. Tieni un borsellino per il tratto attuale. Quando il borsellino va in negativo, portartelo dietro ti fa solo perdere, quindi lo lasci e ricominci da zero. Ricordi anche il borsellino più pieno che hai mai avuto.
current = max(value, current + value)👛 Tieni il borsellino, o ricomincia se è peggiobest = max(best, current)🏆 Ricorda il borsellino più pieno finoracurrent = best = values[0]🚩 Parti dal primo tratto6💰 Il tratto migliore: 4, -1, 2, 1Il problema del sottoarray massimo chiede la somma più grande di elementi consecutivi in una lista. L'algoritmo di Kadane lo risolve in tempo O(n), tenendo per ogni posizione la somma migliore che finisce lì.
Punti chiave
currentè la somma migliore di una serie che finisce nel valore attuale.current = max(value, current + value)inizia una nuova serie quando quella vecchia farebbe solo scendere la somma.best = max(best, current)tiene la somma migliore vista finora in qualsiasi punto.- Partire con entrambi da
values[0]fa funzionare anche le liste di soli numeri negativi.
Quando si usa?
- Il periodo migliore in serie temporali: profitti, punteggi, temperature.
- Imparare una classica idea di programmazione dinamica in un passaggio.
- Domande da colloquio sugli array.
Quando non serve
- Ti servono inizio e fine della serie migliore: salva anche gli indici, oltre alle somme.
- L'ordine dei valori non ha un significato: allora cercare serie consecutive non ha senso.
Codice di esempio
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Risultato dell'esecuzione
6
Spiegazione del codice
Su ogni elemento, la variabile current sceglie tra due possibilità: iniziare un nuovo tratto da quell'elemento oppure continuare il tratto precedente con current + value. La variabile best conserva la somma più alta vista finora. Con i dati di esempio, il tratto [4, -1, 2, 1] dà la somma massima, 6. L'algoritmo richiede O(n) e usa solo O(1) di memoria.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Partire da 0
Con un input di soli numeri negativi la risposta sarebbe 0, che è sbagliato.
current = best = 0
current = best = values[0]
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Massimo della Finestra Scorrevole Riporta il massimo di ogni finestra di k numeri. Difficile
- Largest Adjacent-Digit Product Take every contiguous window of span digits and multiply its digits. Media