This is a question that I already answered here (and here , a modified version). In both cases, the algorithm was applied to the binary case (zeros and ones), but the modification for arbitrary numbers is quite simple (but, unfortunately, I save the images for the binary version of the problem ). You can do this very efficiently using the two- process linear O(n) time algorithm - n is the number of elements. However, this is not dynamic programming — I think that using dynamic programming here would be awkward and inefficient, after all, because of the difficulties with the decomposition problem, as mentioned in the OP, unless it’s homework - but in this case you You can try to impress with this algorithm :-), because, obviously, there is no faster solution than O(n) .
Algorithm (images depict binary case) :
Suppose you want to find the largest rectangle of free (white) elements.
Here follows an algorithm for passing linear O(n) time (n is the number of elements):
1) in the first pass , go through the columns, from bottom to top, and for each element, indicate the number of consecutive elements available before that:
repeat until:
Images depict binary case. In the case of arbitrary numbers, you hold 2 matrices - first with the original numbers, and the second with additional numbers, which are filled with the image above. You must check the original matrix, and if you find a number different from the previous one, you will start numbering again (in the auxiliary matrix) from 1.
2) in the second pass, you go through the lines, maintaining the data structure of potential rectangles, i.e. rectangles containing the current position somewhere on the top edge. See the following image (current position of 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 with height k ). This data structure can be represented by an array with a double linked list linking busy elements, and the size of the array will be limited by the height of the matrix.
Pseudo-code of the second pass (not a 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
Rectangle close function:
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 max rectangles. So, in the end you will get:
And what will be the difficulty? You see that the close_potential_rectangles_higher_than function is O(1) for each closed rectangle. Since for each field we create 1 potential rectangle at the maximum, the total number of potential rectangles ever present on a particular line never exceeds the line length. Therefore, the complexity of this function O(1) amortized!
Thus, the complexity is O(n) , where n is the number of matrix elements.