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 puo’ 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 e’ il negativo -9, altrimenti -9 farebbe parte della sequenza

(solfinal)

Ulteriori info su queste slide.

Next Section - Sottoarray e Sottoinsieme di Somma Fissata