二维矩阵中的最大和矩形 PYTHON

Question

正如标题所说，我正在 python 的二维矩阵中寻找最大和矩形的解决方案，但我对 Kadanes 算法不感兴趣，我正在寻找具有许多循环的所谓“朴素解决方案”。怎么做？

Answer 1

这是朴素的算法：有 4 个变量确定子矩阵：它

顶行
左栏
最后一行
右栏

这意味着您将有四个嵌套循环来查找这些参数的所有可能组合。

然后，为每个子矩阵计算总和。这意味着您将访问每个子矩阵中的每个单元格。你将有一个循环：

子矩阵中的每一行
子矩阵中的每一列

所以总共有 6 个循环。它看起来像这样：

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

二维矩阵中的最大和矩形 PYTHON

Maximum sum rectangle in a 2D matrix PYTHON

python

algorithm

solution