找到面积最大的矩形适合空空间的最有效算法是什么？

假设屏幕看起来像这样("＃"代表填充区域)：

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

一个可能的解决方案是：

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

通常，我很乐于找出解决方案。尽管这一次我想避免浪费自己的时间，因为这在我正在从事的项目中具有实际用途。有众所周知的解决方案吗？

Shog9写道：

Is your input an array (as implied by the other responses), or a list of occlusions in the form of arbitrarily sized, positioned rectangles (as might be the case in a windowing system when dealing with window positions)?

是的，我有一个结构，可以跟踪屏幕上放置的一组窗口。我还有一个网格，可以跟踪每个边缘之间的所有区域(无论它们是空的还是填充的)以及它们的左边缘或者上边缘的像素位置。我认为有一些修改后的表格可以利用此属性。你知道吗

解决方案

回答

这是一个包含一些代码和分析的页面。

特定问题在页面上开始有点向下，在页面上搜索文本最大矩形问题。

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module6/module6.html

回答

@lassevk

// 4. Outer double-for-loop to consider all possible positions 
    //    for topleft corner. 
    for (int i=0; i < M; i++) {
      for (int j=0; j < N; j++) {

        // 2.1 With (i,j) as topleft, consider all possible bottom-right corners. 

        for (int a=i; a < M; a++) {
          for (int b=j; b < N; b++) {

哈哈... O(m2 n2)..那可能就是我想要的。

我看到他们继续进行优化...看起来不错，我会读一读。

回答

@lassevk

我从DDJ找到了引用的文章：最大矩形问题