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