Largest Rectangular Area in a Histogram

int getMaxArea(int hist[], int n)

{

    stack<int> s;

    int max_area = 0;

    int tp;  // To store top of stack

    int area_with_top;

    int i = 0;

    while (i < n)

    {

        // If this bar is higher than the bar on top stack, push it to stack

        if (s.empty() || hist[s.top()] <= hist[i])

            s.push(i++);

        // If this bar is lower than top of stack, then calculate area of rectangle

        // with stack top as the smallest (or minimum height) bar.


        else

        {

            tp = s.top();  // store the top index

            s.pop();  // pop the top

            // Calculate the area with hist[tp] stack as smallest bar

            area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);

            if (max_area < area_with_top)

                max_area = area_with_top;

        }

    }

    // Now pop the remaining bars from stack and calculate area with every

    // popped bar as the smallest bar

    while (s.empty() == false)

    {

        tp = s.top();

        s.pop();

        area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);

        if (max_area < area_with_top)

            max_area = area_with_top;

    }

    return max_area;

}