Per risolvere questo problema ho provato a precalcolarmi tutte le possibili somme e se non ho sbagliato le mie considerazioni dovrei esserci riuscito. Ho costruito una matrice nella cui colonna 0 si trova la sequenza.
Poi scendendo per riga ho seguito una procedura che mi ha portato a questo risultato:
11
-4 7
52 48 59
-7 45 41 52
-2 -9 43 39 50
-20 -22 -29 23 19 30
dove 7 è la somma di -4 e 11, 48 è la somma di 52 e -4, 59 è la somma di 52 e 7 e così via.
Osservando le diagonali, penso di aver notato qualche proprietà.
Prendendo la diagonale maggiore, la somma massima in valore assoluto è il massimo all’interno di questa, cioè 59.
Prendendo la diagonale con dimensione immediatamente inferiore, la somma massima è uguale al suo max + 11.
Procedendo così sembrerebbe che la somma massima sia sempre uguale al max della diagonale più l’ultimo elemento della riga sopra l’ultimo elemento della diagonale. -29+ 59, -22 + 52 e -20 +50 sembrerebbero confermare questa ipotesi, dando il risultato previsto dal caso d’esempio.
In realtà credo serva qualche attenzione in più quando sono presenti numeri negativi, i valori assoluti potrebbero diminuire piuttosto che aumentare.
Il problema più grosso è però dimostrare che posso ottenere il valore da sommare al max di diagonale attraverso somme che di per sé non eccedano il valore max. Non credo che questo possa essere vero, e qui le mie idee cominciano a confondersi.
Sono completamente fuori strada? Qualcuno potrebbe darmi una mano prima dell’inizio delle OII? 