Largest Rectangular Area in a Histogram

Given n numbers representing the heights of bars in a histogram, you are asked to calculate the largest area that can be obtained in the histogram without going out of the bars.
All the bars in the histogram have a width of 1, while the heights are arbitrary nonnegative integers.
notion image


The first line of the input contains a single integer n (1 ≀ n ≀ ).
The next line contains n space-separated integers (0 ≀ ≀ ).


The program should print the largest area possible to obtain from the bars of the histogram.


8 6 2 5 4 5 1 6 1
For each element in the histogram, you can calculate 2 numbers - the closest element that’s smaller than the current element on the left and on the right. That would be sufficient to calculate the area of the rectangle having the height of the current bar.


Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue