Question
Largest Rectangle in a Histogram
You are given an array containing n integers, where each integer represents the height of a histogram bar. Your task is to find the area of the largest rectangle that can be formed within the histogram. The rectangle must be formed by consecutive bars.
In other words, find the largest possible rectangle such that:
-
It spans over one or more adjacent bars.
-
Its height is limited by the shortest bar in that span.
-
Its width is equal to the number of bars in that span.
Return the area of this rectangle.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of bars in the histogram.
The second line contains KaTeX can only parse string typed expression integers, representing the heights of the bars — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers, representing the heights of the bars — KaTeX can only parse string typed expression.
Output
Print a single integer — the area of the largest rectangle in the histogram.
Example
Input
7
2 1 5 6 2 3 1
Output
10
Explanation
The largest rectangle is formed by bars with heights KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, spanning indices 2 to 3 (0-based).
Area = KaTeX can only parse string typed expression
7
2 1 5 6 2 3 1
Output
10
Explanation
The largest rectangle is formed by bars with heights KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, spanning indices 2 to 3 (0-based).
Area = KaTeX can only parse string typed expression