Problema del segmento di somma massima
(da appunti del Prof. Ferragina)

Sia data una sequenza di $n$ interi $S = -7, 4, -8, 3, 4, -2, 6, -10, 1, 3, -3, 9$ (nell'esempio, $n=12$), memorizzata come un array $S \equiv S[1 \dots n]$ (per semplicità, almeno un intero è positivo). Un segmento $S[i \dots j]$ denota una porzione di elementi contigui in $S$, dalla posizione $i$ fino alla posizione $j$ (inclusa). La somma di un segmento $\mathit{somma}(S[i\dots j])$ è data dalla somma dei suoi componenti: $\sum_{k=i}^j S[k]$. Il problema consiste nell'individuare un segmento di somma massima, dove a parità di somma viene scelto il segmento più corto possibile. Nell'esempio, $S[4 \dots 7] = 3, 4, -2, 6$ fornisce somma massima, di valore 11. Osservare che il segmento di somma massima non necessariamente contiene il massimo elemento.

Soluzione 1:

Immaginando di avere una libreria che genera tutti i possibili sotto-insiemi di $S$, possiamo verificare quali tra questi sono dei segmenti (ovvero contengono tutti elementi contigui in $S$). In tal caso, ne calcoliamo la somma e prendiamo la massima tra le somme così ottenute. Svantaggio: inefficienza dovuta all'esame di $2^n$ sottoinsiemi.

Soluzione 2:

Generare solo i segmenti di $S$. 
max <- (-infinito)     // un intero sufficientemente piccolo
for i <- 1 to n do
   for j <- i to n do  // esamina il segmento S[i...j]
      somma <- 0;
      for k <- i to j do
         somma <- somma + S[k]
      // ora somma = somma(S[i...j])
      if somma > max then max <- somma 
      // volendo, si possono memorizzare anche i e j

Costo: $(\sum_{i=1}^n (\sum_{j=i}^n (\sum_{k=i}^j \mathit{costante}))) \sim n^3$.

Svantaggio: non si utilizza $\mathit{somma}(S[i\dots j])$ per il calcolo di $\mathit{somma}(S[i\dots j+1])$.

Soluzione 3:

Sfruttare la relazione $\mathit{somma}(S[i\dots j]) = \mathit{somma}(S[i\dots j-1]) + S[j]$. 
max <- (-infinito)     // un intero sufficientemente piccolo
for i <- 1 to n do
   somma <- 0;
   for j <- i to n do  // esamina il segmento S[i...j]
      somma <- somma + S[j]
      // ora somma = somma(S[i...j])
      if somma > max then max <- somma
      // volendo, si possono memorizzare anche i e j

Costo: $(\sum_{i=1}^n (\sum_{j=i}^n \mathit{costante})) \sim n^2$.

Svantaggio: non si sfrutta pienamente la struttura del problema.

Soluzione 4:

Sia $S[i...j]$ uno dei segmenti di somma massima (e lunghezza minima). La massimalità della somma di $S[i...j]$ implica che:
(a)
$\mathit{somma}(S[i...k]) > 0$ per $i \leq k < j$. Se così non fosse, si avrebbe che $\mathit{somma}(S[i...j]) \leq \mathit{somma}(S[k+1...j])$ (assurdo, un segmento più corto!).
(b)
$\mathit{somma}(S[k...i-1]) \leq 0$ per $1 \leq k \leq i-1$. Se così non fosse, si avrebbe che esiste $k \in [1 \dots i-1]$ con $\mathit{somma}(S[k...i-1]) > 0$ e, quindi, $\mathit{somma}(S[i...j]) < \mathit{somma}(S[k...j])$ (assurdo, un segmento con somma sicuramente maggiore!).
Durante la scansione di $S$, quando somma diventa negativa o nulla, si può considerare un nuovo segmento disgiunto da quelli considerati precedentemente: 
max <- (-infinito)     // un intero sufficientemente piccolo
somma <- (-infinito)
for j <- 1 to n do
   if somma <= 0 then i <- j, somma <- S[j] // caso (b)
                 else somma <- somma + S[j] // caso (a)
   // ora somma = somma(S[i...j])
   if somma > max then max = somma
   // volendo, si possono memorizzare anche i e j
Costo: $(\sum_{j=1}^n \mathit{costante}) \sim n$.

Roberto Grossi, Ottobre 2003.