Largest Histogram Rectangle - Classic Problems | Repovive

CLS59. Largest Histogram Rectangle

2s256 MB

Given bar heights of a histogram, find the largest rectangle area that can be formed using contiguous bars.

\begin{array}{l} n \\ h_1 \quad h_2 \quad \ldots \quad h_n \end{array}

area_{\max}

Input

6
2 1 5 6 2 3

Explanation

The bars with heights 5 and 6 form a rectangle of height 5 and width 2, area 10.

Output

Input

4
4 4 4 4

Explanation

All four bars can be used together, giving area 16.

Output

Input

5
0 2 0 3 3

Explanation

The best rectangle uses the last two bars with height 3, area 6.

Output

\begin{array}{l} n \\ h_1 \quad h_2 \quad \ldots \quad h_n \end{array}

area_{\max}