Sottoarray massimo con l’algoritmo di Kadane
Kadane decide a ogni posizione se continuare o ricominciare.
Che cos’è Sottoarray massimo con l’algoritmo di Kadane?
Kadane decide a ogni posizione se continuare o ricominciare.
Trova il segmento contiguo con somma massima.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Codice di esempio
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]))Output previsto
6Come funziona
Un solo passaggio offre tempo O(n) e memoria O(1).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.