我试图想出一个动态规划算法，发现了一个矩阵，是由相同数量的范围内最大的子矩阵：

例如：

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

答：4个元素，由于基质

  5 5
   5 5
 

解决方案

这是一个问题，我已经回答here （和here,修改后的版本）。在这两种情况下，算法应用到二进制的情况下（零和的），但修改为任意数字是很容易（不过比较遗憾，我把图像问题的二进制版本）。 n为许多元素 - 您可以通过二传的线性 O（N）时间算法做到这一点非常有效。但是，这不是一个动态编程 - 我想用动态规划这里将是笨拙和低效的结束，因为有问题的分解的困难，作为OP提到的 - 除非它的一门功课 - 但在这种情况下，你可以尝试IM preSS该算法:-)因为有比没有明显更快的解决方案 O（N）。

算法（图片描绘二进制情况下）

假设你想找到免费的（白色）元素最大的矩形。

下面如下两通线性 O（N）时间算法（n为elemets数）：

1）中的第一通下，按列去，从底部到顶部，并为每个元素，表示可高达这一个连续元素数：

重复，直到：

图片描绘的二进制情况。对任意数量的你持有2矩阵 - 先用原来的号码，第二个与填充的图像在上面的辅助号码。你必须检查原始矩阵，如果您发现了一些从previous的不一致，你只是从1开始编号（在辅助矩阵）了。

2）在第二遍你去按行，保持电压的矩形数据结构，即包括当前位置在顶部边缘的地方矩形。参见下图（现在的位置是红色，3潜在的矩形 - 紫色 - 身高1，绿色环保 - 身高2和黄色 - 高度3）：

对于每一个我们保持高度 K 和它的左边缘的矩形。换句话说，我们跟踪连续数那名＆GT的款项; = K （即高度潜力的矩形 K ）。该数据结构可以是具有双链表链接占用项psented由阵列重新$ P $，并且阵列大小将由矩阵高度来限定。

伪$ C $的第2次（非二进制版本的任意数字）C：

 变种M [] //原始矩阵
VAR AUX [] //辅助矩阵填补一号通
VAR值为[] //数组潜力矩形，收录他们的身高
           //被占领的项目也上双链表的联系，
           //通过高度有序

的foreach行= 1..1 //去了行
    的foreach COL = 1..M
        如果（COL＆GT; 1和M [行，列] = M [行，列 -  1]！）//新号码
            close_potential_rectangles_higher_than（0）; //关闭所有的矩形

        身高=辅助[行，列] //最大高度可能在当前位置

        如果（！值为[高]）{//矩形的高度不存在
            创建矩形[高] //打开新的矩形
            如果（值为[高]。接下来）//矩形最近的更高高度
                                   //如果存在，从它的左边缘开始
                矩形[高] .left_col =值为[高] .next.left_col
            其他
                矩形[高] .left_col =关口;
        }

        close_potential_rectangles_higher_than（高度）
    结束了//结束行
    close_potential_rectangles_higher_than（0）;
        //行的结束 - ＆GT;关闭所有矩形，假定COL是M + 1吧！

结束了//结束矩阵
 

该函数用于关闭矩形：

 函数close_potential_rectangles_higher_than（高度）
    close_r =矩形高度最高（DLL中的最后一项）
    而（close_r.height＆GT;高度）{//高？关上它
        面积= close_r.height *（COL  -  close_r.left_col）
        如果（区＆GT; max_area）{//我们有最大的矩形！
            max_area =面积
            max_topleft = [行，close_r.left_col]
            max_bottomright = [行+高 -  1，COL  -  1]
        }
        close_r = close_r。preV
        //从双向链表中删除矩形close_r
    }
端功能
 

此方式，您还可以得到所有最大的矩形。那么，到底你：

和什么样的复杂性将是什么？你看，函数 close_potential_rectangles_higher_than 是 O（1）每闭合矩形。因为为每个字段我们创造1电位的矩形在最大的，潜在的矩形的总数目不断present在特定行决不会比该行的长度更高。因此，该功能的复杂性是 O（1）摊销！

所以整个复杂 O（N），其中n为矩阵元素的数量。

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:

example:

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

Answer : 4 elements due to the matrix

   5 5 
   5 5   

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).

Algorithm (pictures depict binary case):

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

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

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:

repeat, until:

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) 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):

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

The function for closing rectangles:

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:

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!

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