Maximum sum rectangle in a 2D matrix PYTHON

Question

As title says i'm looking for solution of maximum sum rectangle in a 2d matrix in python, but im not intereseted in Kadanes algorithm, im looking for so called "naive solution" with many loops. How to do that ?

Answer 1

Here is the naive algorithm: there are 4 variables that determine a submatrix: its

• top row
• left column
• bottom row
• right column

So that means you'll have four nested loops to find all possible combinations of these parameters.

Then, for each of those submatrixes you calculate the sum. This means you will visit each cell in each submatrix. You'll have a loop over:

• each row in the submatrix
• each column in the submatrix

So in total you'll have 6 loops. It looks like this:

m = [
    [ 1,  2, -1, -4, -20],
    [-8, -3,  4,  2,   1],
    [ 3,  8, 10,  1,   3],
    [-4, -1,  1,  7,  -6]
]

maxsum = 0
for top in range(0, len(m)):
    for left in range(0, len(m[0])):
        for bottom in range(top, len(m)):
            for right in range(left, len(m[0])):
                thissum = 0
                for row in range(top, bottom+1):
                    for col in range(left, right+1):
                        thissum += m[row][col]
                maxsum = max(thissum, maxsum)
print(maxsum)  # 29