d065. P-5-7. 大樓外牆廣告

內容

有一條長街林立著許多大樓，每棟樓高高低低不一定，但寬度都是相同。現在想在牆面上找一塊面積最大的矩形來作外牆廣告，此矩形的一對邊必須平行地面，假設每一棟樓的寬度都是 $ 1 $ 單位。

假設有六棟樓，

高度依序為 $(2,1,5,6,2,3)$，

最大矩形應為第 $3$、$4$ 棟樓之間，高度為 $5$，面積為 $10$ 。

輸入說明

第一行 $ n $ ，代表有 $ n $ 棟樓，

第二行有 $ n $ 個非負整數，依序代表從左到右每棟樓的高度。

$ n $ 不超過 $ 1e5 $ ，樓高不超過 $ 1e8 $ 。

輸出說明

最大矩形的面積。

範例輸入 #1

6
2 1 5 6 2 3

範例輸出 #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

標籤:

分治

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」