Largest Rectangle in a Histogram

Difficulty: 1900 3500 ms 128 MB

stack

Bars of width 1 and given heights stand in a row. Print the area of the largest axis-aligned rectangle fitting inside the histogram.

Input: the first line has N; the second line has the N heights.

Output: the maximum rectangle area.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ h_i ≤ 10⁹

Sample Tests

6
2 1 5 6 2 3

10

2
2 2

4

Read the Editorial