Avete idee su come effettuare una prefix sum in un array 2x2 ? Cioè avendo un array 2x2 in cui ogni cella ha un valore, se voglio avere la somma dei valori contenuti in un sottoarray(sottomatrice) dell’originale, riesco ad ottenerlo in tempo constante.
Per una matrice C NxM qualunque l’idea è la seguente:
ti computi per ogni casella il valore S(x,y), cioè la somma dei valori della sottomatrice dalla casella (0,0) alla casella (x,y).
Per computare S(x,y) in maniera veloce si può notare che, con i dovuti accorgimenti nei casi limite (cioè quanto x = 0 o y = 0), che S(x,y) = S(x-1, y) + S(x,y-1) - S(x-1,y-1) + C(x,y).
Una volta computato S, si può trovare la somma di una sottomatrice qualunque in tempo costante (prova a disegnare).
Prova a risolvere raisins utilizzando anche questo metodo 
Si adesso proverò di capirlo, poi lo volevo usare proprio per velocizzare raisins! Grazie 