我想拿出暴力破解（天真）解决方案，找到1或0的1和0的矩形的最大块，我知道，可以在做到这一点的最佳方式Ø （n）的时间，其中n是矩形的总尺寸。

I'm trying to come up with the bruteforce(naive) solution to find the largest block of 1 or 0 in a rectangle of 1 and 0. I know optimal ways which can do it in O(n) time where n is the total size of rectangle.

1 1 0 1 0 1
1 0 0 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0

在上面的矩形，它是长方形的起价大小6.我在想这个..的（行2，列2）

In the above rectangle, it is rectangle starting at (Row 2, Col 2) of size 6. I was thinking this..

仔细检查每一个元素，然后发现它使通过遍历大小   在这一切的方向。

Go through each element and then find the size it makes by iterating in all directions from it.

难道是暴力破解？会有什么复杂性？我经历了为n的所有元素，但后来我遍历各个方向，多少会这样呢？

Is it bruteforce? What will be the complexity? I'm going through all elements that is n, but then I'm iterating in all directions, how much will that be?

我知道，这个问题已经被问100次，但他们谈论的最优解。我正在寻找的是一个暴力破解解决方案，它的复杂性？

I'm aware that this question has been asked 100 times, but they talk about optimal solutions. What I'm looking for is a bruteforce solution and its complexity?

推荐答案

您描述的算法看起来在某种程度上是这样C code：

The algorithm you described looks somehow like this C code:

//for each entry
for(int x = 0; x < width; ++x)
    for(int y = 0; y < height; ++y)
    {
        char lookFor = entries[x][y];
        int area = 0;
        for(int row = y; row < height; ++row)
        {
            if(entries[x, row] != lookFor)
                break;
            for(int col = x; col < width; ++col)
            {
                if(entries[col, row] != lookFor)
                    break;
                int currentArea = (col - x + 1) * (row - y + 1);
                if(currentArea > area)
                {
                    //save the current rect
                }
            }
        }
    }

有四个嵌套循环。外循环将遍历完全 N 倍（与 N 是项目的数量）。内部循环将遍历宽* F1 和高* F2 倍的平均水平（以 F1 和 F2 是某个常数分数）。该算法的休息时间是固定的，不依赖于问题的规模。

There are four nested loops. The outer loops will iterate exactly n times (with n being the number of entries). The inner loops will iterate width * f1 and height * f2 times in average (with f1 and f2 being some constant fraction). The rest of the algorithm takes constant time and does not depend on the problem size.

因此​​，复杂度 O（N * F1 *宽* F2×高）=为O（n ^ 2），这基本上意味着去各个条目，从那里，再次访问每个条目，不顾一切的条目是否真的需要进行检查或只是一个固定比例，随着问题规模增大。

Therefore, the complexity is O(n * f1 * width * f2 * height) = O(n^2), which essentially means "go to each entry and from there, visit each entry again", regardless of whether all entries really need to be checked or just a constant fraction that increases with the problem size.

上面的解释，假设条目未随机分布，并且对于更大的字段是更有可能找到更大均匀分区域。如果这不是这种情况，并且平均迭代次数用于内环路的所有（例如，对于随机分布的条目）不依赖于场的大小，然后将所得的时间复杂度是 O（n）的

The above explanations assume that the entries are not distributed randomly and that for larger fields it is more likely to find larger homogeneous subregions. If this is not the case and the average iteration count for the inner loops does not depend on the field size at all (e.g. for randomly distributed entries), then the resulting time complexity is O(n)