我有一个相当典型的问题。我知道这里可能有类似的主题，但请理解我是一个初学者，不了解这个问题的不同版本。有时文本中的小差异和算法可能完全不同。所以问题是：
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)。如果我没有错的话，在最坏的情况下它可能不会停止。
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)。
你的解决方案是可行的，而且你对时间复杂度的判断是正确的，确实是 a*b*c*c。 加速的一种方法是，在滑动 c*c 窗口时，不重新计算所有内容，而只减去移出窗口的部分并添加移入窗口的部分。由于你可以在 x 和 y 两个方向上都这样做，所以你可能想要记住一列（或一行）中所有 c*c 正方形的总和，以备将来查找。
我认为使用这里提到的滑动方法可以降低复杂度。
假设在您的情况下，每个优化问题中的a、b、c都是常数（意味着c不是一个优化变量）。
1）从左上角开始，O(c*c)
2）删除最左边的列并添加最右边的列后向右滑动O(c)
3）重复（2）（a-c）次，因此O(c*（a-c）)
4）（1）-（3）的成本约为O(c*c + c*(a-c))
5）您还需要向下滑动并对其他（b-c）行执行此操作，每行成本为O(c)向下滑动和O(c*a)完成一行，总计为O(c*c + c*(a-c)(b-c) + c(a-c) + c*(b-c) )
6）假设a、b>>c，则可以简化为O(b*c*a)
如果有任何错误，请告诉我！