Sottoarray di Somma Massima (in italian)¶

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:

Sottoarray di Somma Massima: Soluzione 1¶

def sommamax( a ):
    max=-1
    for i in range(0, len(a)):
        for j in range(i,len(a)):
            somma=0;
            for z in range(i,j+1):
                somma=somma+a[z]
            if(somma>max):
                max=somma
    return max;

print(sommamax([-1,5,8,-9,4,1]))

(sol1)

Sottoarray di Somma Massima: Soluzione 2¶

def sommamax( a ):
    max=-1
    for i in range(0, len(a)):
        somma=0;
        for j in range(i,len(a)):
            somma=somma+a[j]
            if(somma>max):
                max=somma
    return max;

print(sommamax([-1,5,8,-9,4,1]))

(sol2)

Sottoarray di Somma Massima: Soluzione 3¶

Applichiamo i seguenti due lemmi:

La somma dei valori in ogni prefisso del sottoarray ottimo è positiva, se così 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 è negativo, se così 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

def sommamax( a ):
    max=0
    somma=0
    for i in range(len(a)):
        if(somma > 0):
            somma=somma+a[i];
        else:
            somma=a[i];
        if(somma > max):
            max=somma;
    return max

print(sommamax([-1,5,8,-9,4,1]))

(sol3)

(solfinal)

Next Section - Programming Exercises (in italian)