ヒストグラムにおける最大長方形の面積
ヒストグラムを構成する
n 個の棒の高さが与えられたとき、棒の範囲内で得られる最大の面積を求める問題です。ヒストグラムの各棒の幅はすべて 1 で、高さは任意の非負整数として与えられます。
入力
最初の行には整数
n (1 ≤ n ≤ ) が 1 つ与えられます。次の行には
n 個の整数 (0 ≤ ≤ ) が空白区切りで与えられます。出力
ヒストグラムの棒から得られる最大面積を出力してください。
例
入力 | 出力 |
8
6 2 5 4 5 1 6 1 | 12 |
ヒント
各棒について、左側と右側でその棒より小さい最も近い要素を特定すると、その棒を高さとする長方形の面積を計算するのに十分です。
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB