히스토그램 안에 여러 사각형이 존재하는데, 사각형의 면적은 히스토그램의 높이와 넓이를 구해 이를 곱하면 된다. 높이는 문제에서 정수 배열로 주어지므로, 넓이만을 추가로 계산하면 됩니다. 넓이를 구하기 위해, 배열 i 요소에서 왼쪽으로 i 요소의 높이값보다 작은 값이 나올때가지 계속 진행하여 i 높이보다 같거나 큰 요소까지 포함시킨다. 오른쪽도 마찬가리로 i 높이보다 같거나 큰 요소까지 구한후, 전체 넓이가 나오면 이를 높이와 곱해 면적을 구한다. 이렇게 배열요소 i에 대해 면적을 구할 수 있으므로, 이를 전체 배열에 루프를 돌면 계산한 후, 최대를 찾아내면 된다. 이 방식은 O(N^2)의 방식이다.

public void RunTest()
{
    int[] A = { 3, 5, 4, 6, 4, 2, 1 };
    int max = GetMaxAreaInHistogram(A);
    Console.WriteLine(max);
}

public int GetMaxAreaInHistogram(int[] A)
{
    int max = 0;
    for (int i = 0; i < A.Length; i++)
    {
        int area = GetArea(A, i);
        Console.WriteLine("{0}: {1}", i, area);

        max = Math.Max(max, area);
    }
    return max;
}

int GetArea(int[] A, int index)
{
    // check left
    int left = 0;
    for (int i = index - 1; i >= 0; i--)
    {
        if (A[i] < A[index]) break;
        left++;
    }

    // check right
    int right = 0;
    for (int i = index + 1; i < A.Length; i++)
    {
        if (A[i] < A[index]) break;                
        right++;
    }

    // calc area
    int area = (left + right + 1) * A[index];
    return area;
}

보다 효율적인 방식으로 Stack을 사용하여 배열요소 좌측과 우측 넓이를 미리 계산한 후, 차후 면적을 구하는 아래와 같은 방식(O(N))이 있다.

public int GetMaxAreaInHistogram2(int[] A)
{
    Stack<int> S = new Stack<int>();
    int[] W = new int[A.Length];
    int t;

    for (int i = 0; i < A.Length; i++)
    {
        while (S.Count > 0)
        {
            if (A[i] <= A[S.Peek()])
                S.Pop();
            else
                break;
        }

        t = (S.Count == 0) ? -1 : S.Peek();
        W[i] = i - t - 1;
        S.Push(i);
    }

    S.Clear();

    for (int i = A.Length - 1; i >= 0; i--)
    {
        while (S.Count > 0)
        {
            if (A[i] <= A[S.Peek()])
                S.Pop();
            else
                break;
        }

        t = (S.Count == 0) ? A.Length : S.Peek();
        W[i] += t - i - 1;
        S.Push(i);
    }

    int max = 0;
    for (int i = 0; i < A.Length; i++)
    {
        int area = A[i] * (W[i] + 1);
        //Console.WriteLine("{0}: {1}", i, area);
        max = Math.Max(area, max);
    }
    return max;
}