d067. P_5_7 大樓外牆廣告 (分治版)

Content

有一條長街林立著許多大樓，每棟樓高高低低不一定，但寬度都是相同。現在想在牆面上找一塊面積最大的矩形來作外牆廣告，此矩形的一對邊必須平行地面，假設每一棟樓的寬度都是 $1$ 單位。以右圖為例，有六棟樓，高度依序為$(2,1,5,6,2,3)$ ，最大矩形如圖中標示的部分，面積為 $10$。

Input

第一行 $n$，代表有 $n$ 棟樓，第二行有 $n$ 個非負整數，依序代表從左到右每棟樓的高度。$n$ 不超過 $10^5$，樓高不超過 $10^8$。

Output

最大矩形的面積。

Sample Input #1

6
2 1 5 6 2 3

Sample Output #1

測資資訊：

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

Hint ：

Tags:

ch5

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

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