Largest Rectangular Area in a Histogram

Problem :

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. All bars have same width and the width is 1 unit.

For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 2, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)

Solution:

A straightforward answer is to go for each bar in the histogram and find the maximum possible area in histogram for it. Finally find the maximum of these values. This will require O(n^2) time. We would solve this problem in O(n) time complexity.

There are a few invariants that we can use for this problem :

1. If we include bar i, maximum possible height of rectangle including that bar will be h(i), height of that bar.
2. If we include bar i, maximum possible width of rectangle including that bar will be L + R + 1, where :
1. L is the number of adjacent bars to the left of ith bar and height greater than or equal to h(i)
2. R is the number of adjacent bars to the right of ith bar and height greater than or equal to h(i)

Now our task remains as follows:
1) Get Li
2) Get Ri
3) Get area of rectangle for bar i : A(i) = h(i) * (Li + Ri + 1)
4) Fid maximum value of A(i)

Here is the Java code :