Sottoarray di Somma Massima¶
Dato un array di n interi, individuare il sottoarray di somma massima.
Esempio: -1 5 8 -9 4 1
Deve produrre 5+8=13
Sono possibili almeno 3 soluzioni:
Soluzione 1: Tutte le sottosequenze¶
(sol1)
Soluzione 2: Riusando le sottosequenze¶
(sol2)
Soluzione 3: Sfruttando proprietà¶
Applichiamo i seguenti due lemmi:
- La somma dei valori in ogni prefisso del sottoarray ottimo è positiva, se così non fosse potremmo eliminare tale prefisso ottenendo un sottoarray di somma maggiore (assurdo). Esempio: in -1,5,8 il valore -1 può essere tolto
- Il valore immediatamente precedente al primo valore del sottoarray ottimo è negativo, se così non fosse potremmo aggiungere tale valore ottenendo un sottoarray di somma maggiore (assurdo). Esempio: in 5,8 il valore successivo è il negativo -9, altrimenti -9 farebbe parte della sequenza
(solfinal)
Ulteriori info su queste slide.