二维矩阵内大小为 HxW 的最大子数组

Question

给定一个正整数的二维数组，找到大小为 HxW 且总和最大的子矩形。矩形的总和是该矩形中所有元素的总和。

输入： 具有正元素的 2D 数组 NxN 子矩形的 HxW 大小

输出： 具有最大元素和的 HxW 大小的子矩阵。

我已经使用暴力方法解决了这个问题，但是，我现在正在寻找具有更好复杂性的更好解决方案（我的暴力方法的复杂度是 O(n ⁶ )）。

Answer 1

首先创建矩阵的累积和：O(n ² )

Matrix
2 4 5 6
2 3 1 4
2 0 2 1

Cumulative sum
2 6  11 17
4 11 17 27
6 13 21 32

cumulative_sum(i,j)是 中所有元素的总和submatrix (0:i,0:j)。您可以使用以下逻辑计算累积和矩阵：

cumulative_sum(i,j) = cumulative_sum(i-1,j) + cumulative_sum(i,j-1) - cumulative_sum(i-1,j-1) + matrix(i,j)

使用累积和矩阵，您可以在 O(1) 中计算每个子矩阵的和：

calculating sum of submatrix (r1 ... r2 , c1 ... c2)
sum_sub = cumulative_sum(r2,c2) - cumulative_sum(r1-1,c2) - cumulative_sum(r2,c1-1) + cumulative_sum(r1-1,c1-1)

然后使用两个循环，您可以将硬件矩形的左上角放在矩阵的每个点上，并计算该矩形的总和。

for r1=0->n_rows
   for c1=0->n_cols
       r2 = r1 + height - 1
       c2 = c1 + width - 1
       if valid(r1,c1,r2,c2) // doesn't exceed the original matrix
            sum_sub = ... // formula mentioned above
            best = max(sum_sub, best)
return best

这种方法的时间复杂度为O(N ² )。

这是Python的实现：

Matrix
2 4 5 6
2 3 1 4
2 0 2 1

Cumulative sum
2 6  11 17
4 11 17 27
6 13 21 32

输出

maximum sum is: 16
top left corner on: (0, 2)