As I will comment later, it is not completely without merits, either.

Let "i" and "j" be two indices which run from 1 to N. Given a pair (i, j), a unique rectangle (with the maximum possible area, given the indices) that is inscribed within the histogram can be identified.

In the figure above, if i = 2, and j = 3, this rectangle has dimensions 2*4. Similarly if i = 3, and j = 6, this rectangle has dimensions of 4*2. Or more generally (j - i + 1) * MinHeight(i, j), where MinHeight(i, j) is the minimum height of columns between i and j.

If maxRect represents the rectangle with the maximum area, h(i) the height of column i, then one can write an algorithm that looks something like:

**maxRect = max{h(i)} # initialize = tallest column**

**for i = 1 to N-1**

**minHeight(i) = h(i) # between i and current "j"**

**for j = i+1 to N**

**minHeight(i) = min(h(j), minHeight(i))**

**area = (j - i + 1) * minHeight(i)**

**if(area > maxRect.area)**

**maxRect = Rect(i, j) # rectangle(i,j)**

**endif**

**endfor**

**endfor**

This is an order O(N^2) algorithm, which is not terribly impressive. We can do much better, at least O(N log N).

However, before we write this off as a bad algorithm, I want to point out three redeeming features.

One, its memory footprint is small. Two, the algorithm is eminently "parallelizable". And three, it is simple to understand and maintain.

So in a world with different constraints, it may still have a chance.

## No comments:

Post a Comment