算法來尋找最大子陣列（矩形）的區域完全由1的

Question

有一個2D二進制數組（的0和1 2D陣列），其中m行和列n;給出一個有效的算法來尋找完全由1 s組成的最大子陣列（矩形）的面積。

public int findMaxRectangleArea(int[][] A,int m,int n); 

有人可以幫助我的算法部分？

Answer 1

這一切都取決於你的離子最小陣列尺寸有多大。如果它小於目標平臺上的最大單詞大小，則可以將陣列製作成一維位圖陣列，並使用一系列滑動位圖遮罩窗口來查找矩形。

Answer 2

我想嘗試這樣的做法：

迭代左至右逐列，直到找到一個0。

這0可能已經確定的1的兩個矩形：

• 它上面的所有行從頂部
• 留給位置的0

其中一人左更大，記住它。

然後遞歸下降到三個未知部門（其中兩個部分未知）可能仍然包含一個矩形比更大的你已經發現：

確保你不要重複遍歷已知的行，這是多餘的。

我相信這個解決方案可以看看每場最多兩次（其中一個遞歸步驟的部門重疊），所以應該在θ（X * Y）上運行。