題意

給定一個由01組成的矩形，要求找出矩形內由1組成的面積最大的矩形面積。

思路

之前寫過一道類似的題，由若干個長度為1，高度不同的矩形連在一起，求最大矩形面積。這道題其實是類似的，我們只需要預處理出在位置[i, j]上，最大的1的高度，然后一行一行的處理，就和之前那道題相同了。

狀態表示：

h[i,j]$h[i, j]$，位置[i, j]上1的最大高度。

l[i,j]$l[i, j]$，位置[i, j]上，以h[i, j]為高度能向左延伸多少。

r[i,j]$r[i, j]$，在位置[i, j]上，以當前高度能向右延伸多少。

轉移方程：

h[i,j]$h[i, j]$直接預處理一下即可。

l[i,j]$l[i, j]$：

r[i,j]$r[i, j]$：

計算方法同l[i,j]$l[i, j]$

代碼