广场与矩阵最大的一笔 [英] Square with largest sum in the matrix

问题描述

我有很典型的问题，我想。我知道这里有相似的主题，但明白，我是个初学者，不区分不同版本的问题。在文本和算法有时差别不大可以完全不同。所以，问题是：

I've got quite typical problem, I think. I know there were similar topics here but understand that I'm a beginner and do not distinguish different versions of this problem. Sometimes little difference in text and the algorithm can be completely different.. So the problem is:

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）。如果我没有错，在最坏的情况下可能不会停止。

I can write an algorithm that runs the entire matrix and on every point(x,y) it counts sum for a square (x,y), (x+c,y), (x,y+c), (x+c,y+c). Then I chose the largest sum. With these constraints I think it could be quite fast, but is there any faster algorithm? I'm not good at counting algorithm complexity but it seems to be O(a*b*c*c). And if I'm not wrong in the worst case it may not stop..

推荐答案

我认为正确的方式来处理，这是做一个整体的第一变换：原矩阵M的每个元素（I，J），计算积分变换矩阵 I（I，J）= SUM [0..i，0..j]（M）。通过在这两个行和列的方向运行总和，你可以在O（A * B）的时间。这样做

I believe the right way to approach this is to do an integral transform first: for each element (i,j) of the original matrix M, compute integral transform matrix I(i,j) = sum[0..i, 0..j](M). By running sums in both the rows and columns directions, you can do this in O(a*b) time.

一旦你的积分变换，你可以计算的总和的的任意子块的在固定时间为：

Once you have the integral transform, you can compute the sum of any sub-block in constant time as:

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）的

so you can compute and compare each c x c square sum in constant time, for a total of O(a*b).

这篇关于广场与矩阵最大的一笔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！