Largest Rectangle in Histogram

Given bar heights of a histogram (each bar has width 1), find the area of the largest rectangle that fits entirely within the histogram's outline.

Example

Input: 2 1 5 6 2 3 Output: 10 (bars of height 5 and 6, width 2, area 10)

Approach

This is the hardest of the classic monotonic-stack problems. Keep a stack of indices with increasing heights. When a shorter bar arrives, every taller bar still on the stack can't extend any further right — pop it and compute the rectangle it forms, using the new stack top (or the array start, if the stack empties) as the left boundary and the current index as the right boundary. Appending a sentinel height of 0 at the end forces every remaining bar on the stack to be resolved before the algorithm finishes.

Input format

Line 1: the heights, space-separated

Print the maximum area.