我将逐步介绍一些增加难度/降低运行时复杂度的解决方案。
首先，解决暴力问题。生成每个可能的矩形。您可以通过迭代r1≤r2和c1≤c2的每对点（r1，c1）（r2，c2）来完成此操作（可以使用4个for循环来完成）。如果矩形不包含0，则将面积与迄今为止找到的最大面积进行比较。这是O（R
^ 3C ^ 3）。
我们可以将有效的矩形检查加快到O（1）。我们通过执行DP来做到这一点，其中dp（r，c）在矩形（（1，1），（r，c））中存储0的数目。
- dp（r，0）= 0
- dp（0，c）= 0
- dp（r，c）= dp（r-1，c）+ dp（r，c-1）-dp（r-1，c-1）+（矩阵[r] [c]？0：1）
那么（（r1，c1），（r2，c2））中的0数为
- nzeroes（r1，c1，r2，c2）= dp [r2] [c2] -dp [r1 -1] [c2] -dp [r2] [c1 -1] + dp [r1 -1] [c1 -1]
然后，可以通过nzeroes（r1，c1，r2，c2）== 0检查矩形是否有效。
为此，有一个使用简单的DP和堆栈的O（R ^ 2C）解决方案。DP通过找到一个单元格上方的1个单元格的数量直到下一个0来对每列工作。dp如下：
- dp（r，0）= 0
- 如果matrix [r] [c] == 0，则dp（r，c）= 0
- dp（r，c）= dp（r-1，c）+ 1否则
然后，您执行以下操作：
area = 0for each row r: stack = {} stack.push((height=0, column=0)) for each column c: height = dp(r, c) c1 = c while stack.top.height > height: c1 = stack.top.column stack.pop() if stack.top.height != height: stack.push((height=height, column=c1)) for item in stack: a = (c - item.column + 1) * item.height area = max(area, a)也可以使用三个DP解决O（RC）中的问题：
- h（r，c）：如果我们从（r，c）开始并向上走，在第一个0之前我们找到多少个单元格？
- l（r，c）：我们可以在（r，c）和高度h（r，c）处扩展一个具有右下角的矩形吗？
- r（r，c）：我们可以在（r，c）和高度h（r，c）的左下角延伸一个矩形到多远？
三种重复关系是：
- h（0，c）= 0
- 如果matrix [r] [c] == 0，则h（r，c）= 0
h（r，c）= h（r-1，c）+1否则
l（r，0）= 0
如果矩阵[r-1] [c] == 0，则l（r，c）= cp
l（r，c）= min（l（r − 1，c），c − p）否则
r（r，C + 1）= 0
如果矩阵[r-1] [c] == 0，则r（r，c）= pc
- r（r，c）= min（r（r − 1，c），p − c）否则
其中p是上一个0的列，因为我们从左至右填充l，从右至左填充r。
答案是：
- max_r，c（h（r，c）*（l（r，c）+ r（r，c）− 1））
之所以如此行事，是因为观察到最大的矩形在所有四个侧面上始终会接触到0（将边缘视为被0覆盖）。通过考虑所有顶部，左侧和右侧至少接触0的矩形，我们覆盖了所有候选矩形。生成每个可能的矩形。您可以通过迭代r1≤r2和c1≤c2的每对点（r1，c1）（r2，c2）来完成此操作（可以使用4个for循环来完成）。如果矩形不包含0，则将面积与迄今为止找到的最大面积进行比较。
注意：我是根据我在这里写下的答案改编以上内容的-
请参阅“ Ben的妈妈”部分。在该文章中，0为树。该文章也具有更好的格式。
