我认为我遇到了非常典型的问题。我知道这里有类似的主题，但知道我是初学者，不区分这个问题的不同版本。有时文本和算法的细微差别可能完全不同..所以问题是：
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)。如果我在最坏的情况下没有错，它可能不会停止..
我相信解决这个问题的正确方法是首先进行积分变换：对于原始矩阵 M 的每个元素 (i,j)，计算积分变换矩阵I(i,j) = sum[0..i, 0..j](M)。通过在行和列方向上运行总和，您可以在 O(a*b) 时间内完成此操作。
完成积分变换后，您可以在恒定时间内计算任何子块的总和：
sum[i0..i1, j0..j1](M) = I(i1,j1) - I(i0 - 1, j1) - I(i1, j0 - 1) + I(i0 - 1, j0 - 1)
因此您可以在恒定时间内计算和比较每个 cxc 平方和，总共为 O(a*b)。
您的解决方案将起作用，并且您对时间复杂度的看法是正确的，实际上它是 a*b*c*c。加快一点速度的一种方法是，当您滑动 c*c 窗口时，您不会重新计算所有内容，而只需减去移出窗口的部分，并将移入的部分添加到窗户。由于您可以在方向 x 和方向 y 上执行此操作，因此您可能希望记住一列（或一行）中所有 c*c 平方的总和以供将来查找。
我认为使用此处提到的滑动方法可以降低您的复杂性。因此，假设在您的情况下， a,b,c 在每个优化问题中都是恒定的（意味着 c 不是优化变量）。
1）从左上角开始，O(c*c)
2) 去掉最左边一列，添加最右边一列后向右滑动O(c)
3) 重复 (2) 次 (ac) 次，所以 O(c*(ac))
4) (1)-(3) 成本约为 O(c*c + c*(ac))
5）您还需要向下滑动并为其他（bc）行执行此操作，每行花费O（c）向下滑动并且O（c * a）完成一行，总共是O（c * c + c*(ac) (bc) + c (ac) + c*(bc) )
6) 假设a,b>>c，它可以简化为O(b*c*a)
让我知道是否有任何问题！