#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

class Solution
{
public:
	int getMaxProduct(int *arr, int n)
	{
		if(n < 3)	return 0;
		AllocateMemory(n);	//all memory set to 0
		
		//First calculate the max value that is larger than the current value in the right of each element
		calculateRightMax(arr, n);
		//Secondly calculate the max value that is smaller than the current value in the left of each element
		calculateLeftMax(arr, n);
		
		//Now get maximum of product
		int maxProduct = 0, curProduct = 0;
		for(int i = 1; i < n - 1; ++i)
		{
			curProduct = leftMaxArr[i] * arr[i] * rightMaxArr[i];
			if(curProduct > maxProduct)
				maxProduct = curProduct;
		}
		
		FreeMemory();
		return maxProduct;
	}

private:
	int	*rightMaxArr;
	int *leftMaxArr;
	
	void AllocateMemory(int n)
	{
		leftMaxArr = new int[n<<1];
		rightMaxArr = &leftMaxArr[n];
		memset(leftMaxArr, 0, sizeof(int)*(n<<1));
	}
	
	void FreeMemory()
	{
		delete [] leftMaxArr;
	}
	
	void calculateRightMax(int * arr, int n)
	{
		int maxVal = 0;
		for(int i = n - 1; i >= 0; --i)
		{
			if(maxVal > arr[i])
				rightMaxArr[i] = maxVal;
			else
				maxVal = arr[i];
		}
	}
	
	void calculateLeftMax(int * arr, int n)
	{
		stack<int>	stackA;
		stackA.push(arr[0]);
		int curPos = 1, leftMax = 0;
		while(curPos < n)
		{
			if(rightMaxArr[curPos] == 0)
			{
				++curPos;
				continue;
			}
			
			leftMax = 0;
			while(!stackA.empty() && arr[curPos] >= stackA.top())
			{
				if(arr[curPos] > stackA.top())
					leftMax = stackA.top();
				stackA.pop();
			}
			
			leftMaxArr[curPos] = leftMax;
			stackA.push(arr[curPos++]);
		}
	}
};


int main() {
	int arr1[] = {6, 7, 8, 1, 2, 3, 9, 10};
	int arr2[] = {1, 5, 10, 8, 9};
	
	Solution so;
	cout<<"Output for arr1 is "<<so.getMaxProduct(arr1, sizeof(arr1)/sizeof(int))<<endl<<endl;
	cout<<"Output for arr2 is "<<so.getMaxProduct(arr2, sizeof(arr2)/sizeof(int))<<endl<<endl;
	
	return 0;
}