d065: P-5-7. 大樓外牆廣告
Tags : 分治
Accepted rate : 12人/12人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-08 11:33

Content

有一條長街林立著許多大樓,每棟樓高高低低不一定,但

寬度都是相同。現在想在牆面上找一塊面積最大的矩形

來作外牆廣告,此矩形的一對邊必須平行地面,假設每一

棟樓的寬度都是 1 單位。假設有六棟樓,高度

依序為(2,1,5,6,2,3),最大矩形應為第3、4棟樓之間,高度為5,

面積為10。

 

 

Input

第一行 n,代表有 n 棟樓,第二行有 n 個非負整數,依序代表從左到右

每棟樓的高度。n 不超過 1e5,樓高不超過 1e8。

Output

最大矩形的面積。

Sample Input
6
2 1 5 6 2 3
Sample Output
10
測資資訊:
記憶體限制: 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
Hint :
Tags:
分治
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」