#include <iostream>
#include <stack>
#include <vector>

using namespace std;
/*
**	Check here for algorithm analysis: 
** 	http://tech-queries.blogspot.com/2011/03/maximum-area-rectangle-in-histogram.html
*/

int LargestRectangleArea(vector<int> &height) 
{
    stack<int> sLimit;
    int size = height.size();
	int width[size];

    sLimit.push(-1); //make -1 as sentinel
    //search left boundary for each bar
    for (int i = 0; i < size; ++i)
    {
    	//find the left bar that current bar could reach
    	while(sLimit.top() >= 0)
    	{
    		//find first bar on the left that is less than current one,
    		//we find boundary for this bar
    		if (height[i] > height[sLimit.top()])
    			break;
    		//the bar is larger than current one, no need to compare in the future
    		else //(heigth[i] <= height[hsLimit.top()])
    			sLimit.pop();
    	}

    	width[i] = i - sLimit.top() - 1; //-1 is indicate the current bar is excluded
    	sLimit.push(i);
    }
	
	for (int i = 0; i < size; ++i)
		cout << width[i] << ',';
	cout << endl;

    sLimit = stack<int>();
    sLimit.push(size);
    //search right boundary for each bar
    for (int i = size-1; i >= 0; --i)
    {
    	while(sLimit.top() < size)
    	{
    		if (height[i] > height[sLimit.top()])
    			break;
    		else
    			sLimit.pop();
    	}

    	width[i] += sLimit.top() - i; //no -1 here, include current bar as well
    	sLimit.push(i);
    }
	
	for (int i = 0; i < size; ++i)
		cout << width[i] << ',';
	cout << endl;

    int maxArea = 0;
    for (int i = 0; i < size; ++i)
    {
    	int area = width[i] * height[i];
    	if (area > maxArea) maxArea = area;
    }

    return maxArea;
}


int main(int argc, char** argv)
{
	int A[] = {2,1,2};
	vector<int> Av;

	for (int i = 0; i < sizeof(A)/sizeof(int); ++i)
		Av.push_back(A[i]);
	
	cout << LargestRectangleArea(Av);
	
	return 0;
}