題意

給定一個(gè)由01組成的矩形，要求找出矩形內(nèi)由1組成的面積最大的矩形面積。

思路

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

狀態(tài)表示：

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]上，以當(dāng)前高度能向右延伸多少。

轉(zhuǎn)移方程：

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

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

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

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

代碼