I have an issue.

I need a solution to my problem where I need an algorithm to find the maximum sum in an N x N with a method faster than N^6

The N x N contains both positive and negative numbers.

Something like this:



I thought maybe a divide-and-conquer method could be used, but I'm not sure exactly how that would work.

Any feedback is helpful!

are you looking for the sum of all the values in the matrix?

It's any given N x N matrix with negative and positive numbers.

I need an algorithm that can find the box with the biggest sum, it can be from 1 x 1 to N x N.

The box must be the biggest possible sum of any box in the matrix.

so in this case, 100 is the biggest value?

no, it's much bigger. You need to put together all the numbers in the box, like the grey box gives a sum of 142.

so if you just iterate through the matrix you would just do:

int sum = 0;
for(int row = 0; row < matrix.length; row ++){
for(int col = 0; col < matrix[row].length; col++){
sum += matrix[row][col];
}
}

return sum;

this would add all the values in the matrix together.

Ok, but that is not necessarily the biggest sum in the matrix, there are negative numbers aswell, so I need to sort those out aswell.

ahhh i didnt understand what you were asking. https://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum this seems to be what youre looking for

Yes, that's it thanks.

http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

this could help too!