具有相同数目的最大矩形子矩阵 [英] Largest rectangular sub matrix with the same number

问题描述

我正在尝试提出一种动态规划算法，该算法在由相同数字组成的矩阵中找到最大的子矩阵:

I am trying to come up with a dynamic programming algorithm that finds the largest sub matrix within a matrix that consists of the same number:

示例:

{5 5 8}
{5 5 7}
{3 4 1}

答案:4个元素由于矩阵

Answer : 4 elements due to the matrix

   5 5 
   5 5   

推荐答案

这是我已经回答过的问题 此处(和此处，修改版本).在这两种情况下，算法都应用于二进制大小写(零和一)，但是对任意数字的修改非常容易(但抱歉，我保留了问题的二进制版本的图像).您可以通过两遍线性O(n)时间算法非常有效地做到这一点 - n 是元素的数量.但是，这不是动态编程 - 我认为在这里使用动态编程最终会变得笨拙且效率低下，因为问题分解存在困难，正如 OP 所提到的 - 除非它是作业 - 但在这种情况下，您可以尝试这个算法给我留下了深刻的印象:-) 因为显然没有比 O(n) 更快的解决方案.

This is a question I already answered here (and here, modified version). In both cases the algorithm was applied to binary case (zeros and ones), but the modification for arbitrary numbers is quite easy (but sorry, I keep the images for the binary version of the problem). You can do this very efficiently by two pass linear O(n) time algorithm - n being number of elements. However, this is not a dynamic programming - I think using dynamic programming here would be clumsy and inefficient in the end, because of the difficulties with problem decomposition, as the OP mentioned - unless its a homework - but in that case you can try to impress by this algorithm :-) as there's obviously no faster solution than O(n).

算法(图片描述二进制情况):

假设你想找到最大的自由(白色)元素矩形.

Say you want to find largest rectangle of free (white) elements.

这里遵循两遍线性O(n)时间算法(n是元素的数量):

Here follows the two pass linear O(n) time algorithm (n being number of elemets):

1) 在第一遍中，从下到上逐列，并为每个元素表示直到这个元素可用的连续元素的数量:

1) in a first pass, go by columns, from bottom to top, and for each element, denote the number of consecutive elements available up to this one:

重复，直到:

图片描述了二进制案例.在任意数字的情况下，您持有 2 个矩阵 - 第一个是原始数字，第二个是上图中填充的辅助数字.您必须检查原始矩阵，如果发现与前一个不同的数字，则只需从 1 重新开始编号(在辅助矩阵中).

Pictures depict the binary case. In case of arbitrary numbers you hold 2 matrices - first with the original numbers and second with the auxiliary numbers that are filled in the image above. You have to check the original matrix and if you find a number different from the previous one, you just start the numbering (in the auxiliary matrix) again from 1.

2) 在第二遍中，您按行进行操作，保存潜在矩形的数据结构，即包含当前位置的矩形在顶部边缘的某处.见下图(当前位置为红色，3个潜在矩形-紫色-高度1，绿色-高度2和黄色-高度3):

2) in a second pass you go by rows, holding data structure of potential rectangles, i.e. the rectangles containing current position somewhere at the top edge. See the following picture (current position is red, 3 potential rectangles - purple - height 1, green - height 2 and yellow - height 3):

对于每个矩形，我们保持它的高度 k 和它的左边缘.换句话说，我们跟踪 >= k 的连续数字的总和(即高度为 k 的潜在矩形).这种数据结构可以用双链表链接被占用的项的数组来表示，数组的大小会受到矩阵高度的限制.

For each rectangle we keep its height k and its left edge. In other words we keep track of the sums of consecutive numbers that were >= k (i.e. potential rectangles of height k). This data structure can be represented by an array with double linked list linking occupied items, and the array size would be limited by the matrix height.

第二遍的伪代码(具有任意数字的非二进制版本):

Pseudocode of 2nd pass (non-binary version with arbitrary numbers):

var m[] // original matrix
var aux[] // auxiliary matrix filled in the 1st pass
var rect[] // array of potential rectangles, indexed by their height
           // the occupied items are also linked in double linked list, 
           // ordered by height

foreach row = 1..N // go by rows
    foreach col = 1..M
        if (col > 1 AND m[row, col] != m[row, col - 1]) // new number
            close_potential_rectangles_higher_than(0);  // close all rectangles

        height = aux[row, col] // maximal height possible at current position

        if (!rect[height]) { // rectangle with height does not exist
            create rect[height]    // open new rectangle
            if (rect[height].next) // rectangle with nearest higher height
                                   // if it exists, start from its left edge
                rect[height].left_col = rect[height].next.left_col
            else
                rect[height].left_col = col; 
        }

        close_potential_rectangles_higher_than(height)
    end for // end row
    close_potential_rectangles_higher_than(0);
        // end of row -> close all rect., supposing col is M+1 now!

end for // end matrix

闭合矩形的函数:

function close_potential_rectangles_higher_than(height)
    close_r = rectangle with highest height (last item in dll)
    while (close_r.height > height) { // higher? close it
        area = close_r.height * (col - close_r.left_col)
        if (area > max_area) { // we have maximal rectangle!
            max_area = area
            max_topleft = [row, close_r.left_col]
            max_bottomright = [row + height - 1, col - 1]
        }
        close_r = close_r.prev
        // remove the rectangle close_r from the double linked list
    }
end function

这样你也可以得到所有最大的矩形.所以最后你得到:

This way you can also get all maximum rectangles. So in the end you get:

复杂度是多少?您会看到函数 close_potential_rectangles_higher_than 每个闭合矩形是 O(1).因为对于每个字段，我们最多创建 1 个潜在矩形，因此特定行中曾经存在的潜在矩形总数永远不会大于该行的长度.因此，这个函数的复杂度是O(1)分摊的！

And what the complexity will be? You see that the function close_potential_rectangles_higher_than is O(1) per closed rectangle. Because for each field we create 1 potential rectangle at the maximum, the total number of potential rectangles ever present in particular row is never higher than the length of the row. Therefore, complexity of this function is O(1) amortized!

所以整个复杂度是 O(n)，其中 n 是矩阵元素的数量.

So the whole complexity is O(n) where n is number of matrix elements.

这篇关于具有相同数目的最大矩形子矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！