algorithm - 矩阵中和最大的平方

Question

我认为我有一个非常典型的问题。我知道这里有类似的主题，但明白我是初学者，不会区分这个问题的不同版本。有时文本和算法可能完全不同..所以问题是:

For a given 2<=a,b<=1000 and 1<=c<=Min(a,b) find in matrix a x b square c x c 
with the largest sum of elements. The elements in matrix are from -1000 to 1000.

我可以编写一个算法来运行整个矩阵，并在每个点 (x,y) 上计算正方形 (x,y)、(x+c,y)、(x,y+c) 的总和， (x+c,y+c)。然后我选择了最大的金额。有了这些限制，我认为它可能会非常快，但是有没有更快的算法？我不擅长计算算法的复杂度，但它似乎是 O(a*b*c*c)。如果我没有错，在最坏的情况下它可能不会停止......

Answer 1

我认为解决这个问题的正确方法是首先进行积分变换:对于原始矩阵 M 的每个元素 (i,j)，计算积分变换矩阵 I(i,j) = sum[0 ..i, 0..j](M).通过在行和列两个方向运行求和，您可以在 O(a*b) 时间内完成此操作。

一旦你有了积分变换，你就可以在常数时间内计算任何子 block 的总和:

sum[i0..i1, j0..j1](M) = I(i1,j1) - I(i0 - 1, j1) - I(i1, j0 - 1) + I(i0 - 1, j0 - 1)

因此您可以在常数时间内计算和比较每个 c x c 的平方和，总共为 O(a*b)。