using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Console.WriteLine(HistogramMaximumArea.MaximumAreaOfRectanglesFromHistogramWorst(new int[] { 4, 2, 3, 5, 4 })); // 10

        Console.WriteLine(HistogramMaximumArea.MaximumAreaOfRectanglesFromHistogramWorst(new int[] { 4, 2, 3, 5, 4, 3, 3 })); // 15

        Console.WriteLine(HistogramMaximumArea.MaximumAreaOfRectanglesFromHistogramBest(new int[] { 4, 2, 3, 5, 4 })); // 10

        Console.WriteLine(HistogramMaximumArea.MaximumAreaOfRectanglesFromHistogramBest(new int[] { 4, 2, 3, 5, 4, 3, 3 })); // 15

    }

}

​

class HistogramMaximumArea

{

    // O(N^2)

    public static int MaximumAreaOfRectanglesFromHistogramWorst(int[] histogram)

    {

        int maximumArea = 0;

        foreach (var rect in histogram)

        {

            int maximumWidth = 0, width = 0;

            foreach (var innerRect in histogram)

            {

                if (rect <= innerRect)

                {

                    width++;

                }

                else

                {

                    maximumWidth = maximumWidth > width ? maximumWidth : width;

                    width = 0;

                }

            }

            maximumWidth = maximumWidth > width ? maximumWidth : width;

            var area = maximumWidth * rect;

            maximumArea = maximumArea > area ? maximumArea : area;

        }

        return maximumArea;

    }

    // O(N)

    public static int MaximumAreaOfRectanglesFromHistogramBest(int[] histogram)

    {

        Stack<int> tempStack = new Stack<int>();

        int maximumArea = 0;

        var index = 0;

        tempStack.Push(index);

        for (index = 1; index < histogram.Length; index++)

        {

            if (tempStack.Count == 0 || histogram[tempStack.Peek()] <= histogram[index])

            {

                tempStack.Push(index);

            }

            else

            {

                // Continue POP from Stack while Bar of smaller height is encountered

                // Pop and calculate area as popped bar as smallest bar

                var topIndex = tempStack.Peek();

                tempStack.Pop();

                var area = histogram[topIndex] * (index - tempStack.Count - 1);

                maximumArea = maximumArea > area ? maximumArea : area;

                tempStack.Push(histogram[index]);

            }

        }

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

        // popped bar as the smallest bar

        while (tempStack.Count > 0)

        {

            var topIndex = tempStack.Peek();

            tempStack.Pop();

            var area = histogram[topIndex] * (index - tempStack.Count - 1);

            if (maximumArea < area)

                maximumArea = area;

        }

        return maximumArea;

    }

}