Thursday, January 6, 2011

Histogram Puzzle

I came across an interesting "algorithmic" puzzle, through a colleague of my wife.

Suppose you have a histogram composed of "square tiles" as shown below:
There are N columns (N = 8 in this illustration), and each column has an integral number of tiles. The tallest column has P tiles (P = 9 in this illustration).

The problem is to find a rectangle that is inscribed within the histogram, that has the largest area. In the figure above, this particular rectangle has dimensions 6*2, and an area of 12. Note that there may more than one unique solution. In the figure above, there is another rectangle with dimensions 3*4 (area = 12), which is not outlined.

We want to design an algorithm that enables us to identify all the different inscribed rectangles with maximum area.

No comments: