Cannot calculate sum

#1

int sum_of_submatrices_approach2(int prefix[][5], int m, int n)
{
int sum = 0;

for (int li = 0; li <= m-1; li++)
    for (int lj = 0; lj <= n-1; lj++)
        for (int bi = li; bi <= m-1; bi++)
            for (int bj = lj; bj <= n-1; bj++)
                sum += prefix[bi][bj] - prefix[li-1][bj] - prefix[bi][lj-1] + prefix[li-1][lj-1];                

return sum;

}

For the above code, I’m getting an unusual value (negative value) for sum. Not able to identify the problem. I have calculated the prefix matrix as shown below. a[i][j] is the original matrix.

for (int i = 0; i < m; i++) // To initialize first column of prefix matrix.
prefix[i][0] = a[i][0];

for (int row = 0; row < m; row++)         // Calculate cumulative sum for each row.
    for (int col = 1; col < n; col++)
        prefix[row][col] = prefix[row][col-1] + a[row][col];
    
for (int col = 0; col < m; col++)       // Calculate cumulative sum for each column.
    for (int row = 1; row < n; row++)
        prefix[row][col] = prefix[row-1][col] + prefix[row][col];
#2

this statement may cause error as initially li is 0 so prefix[li-1] will give garbage value
use if condition to avoid this

sum=prefix[bi][bj];
if(li>0) sum-=prefix[li-1][bj];
if(lj>0) sum-=prefix[bi][lj-1];
if(li>0 && lj-1) sum+=prefix[li-1][lj-1];
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.