Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalla strada a pedaggio al codice
current = max(value, current + value)👛 Tieni il borsellino, o ricomincia se è peggio
best = max(best, current)🏆 Ricorda il borsellino più pieno finora
current = best = values[0]🚩 Parti dal primo tratto
6💰 Il tratto migliore: 4, -1, 2, 1
Allunga la serie finché conviene, ricomincia quando non conviene più.
In una frase

Il 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

  1. current è la somma migliore di una serie che finisce nel valore attuale.
  2. current = max(value, current + value) inizia una nuova serie quando quella vecchia farebbe solo scendere la somma.
  3. best = max(best, current) tiene la somma migliore vista finora in qualsiasi punto.
  4. 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

Esegui codice →
main.py
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]))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Partire da 0

Con un input di soli numeri negativi la risposta sarebbe 0, che è sbagliato.

Problema
current = best = 0
Correzione
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.

Tutte le sfide