fork(5) download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. class Solution
  7. {
  8. public:
  9. 	int getMaxProduct(int *arr, int n)
  10. 	{
  11. 		if(n < 3)	return 0;
  12. 		AllocateMemory(n);	//all memory set to 0
  13.  
  14. 		//First calculate the max value that is larger than the current value in the right of each element
  15. 		calculateRightMax(arr, n);
  16. 		//Secondly calculate the max value that is smaller than the current value in the left of each element
  17. 		calculateLeftMax(arr, n);
  18.  
  19. 		//Now get maximum of product
  20. 		int maxProduct = 0, curProduct = 0;
  21. 		for(int i = 1; i < n - 1; ++i)
  22. 		{
  23. 			curProduct = leftMaxArr[i] * arr[i] * rightMaxArr[i];
  24. 			if(curProduct > maxProduct)
  25. 				maxProduct = curProduct;
  26. 		}
  27.  
  28. 		FreeMemory();
  29. 		return maxProduct;
  30. 	}
  31.  
  32. private:
  33. 	int	*rightMaxArr;
  34. 	int *leftMaxArr;
  35.  
  36. 	void AllocateMemory(int n)
  37. 	{
  38. 		leftMaxArr = new int[n<<1];
  39. 		rightMaxArr = &leftMaxArr[n];
  40. 		memset(leftMaxArr, 0, sizeof(int)*(n<<1));
  41. 	}
  42.  
  43. 	void FreeMemory()
  44. 	{
  45. 		delete [] leftMaxArr;
  46. 	}
  47.  
  48. 	void calculateRightMax(int * arr, int n)
  49. 	{
  50. 		int maxVal = 0;
  51. 		for(int i = n - 1; i >= 0; --i)
  52. 		{
  53. 			if(maxVal > arr[i])
  54. 				rightMaxArr[i] = maxVal;
  55. 			else
  56. 				maxVal = arr[i];
  57. 		}
  58. 	}
  59.  
  60. 	void calculateLeftMax(int * arr, int n)
  61. 	{
  62. 		stack<int>	stackA;
  63. 		stackA.push(arr[0]);
  64. 		int curPos = 1, leftMax = 0;
  65. 		while(curPos < n)
  66. 		{
  67. 			if(rightMaxArr[curPos] == 0)
  68. 			{
  69. 				++curPos;
  70. 				continue;
  71. 			}
  72.  
  73. 			leftMax = 0;
  74. 			while(!stackA.empty() && arr[curPos] >= stackA.top())
  75. 			{
  76. 				if(arr[curPos] > stackA.top())
  77. 					leftMax = stackA.top();
  78. 				stackA.pop();
  79. 			}
  80.  
  81. 			leftMaxArr[curPos] = leftMax;
  82. 			stackA.push(arr[curPos++]);
  83. 		}
  84. 	}
  85. };
  86.  
  87.  
  88. int main() {
  89. 	int arr1[] = {6, 7, 8, 1, 2, 3, 9, 10};
  90. 	int arr2[] = {1, 5, 10, 8, 9};
  91.  
  92. 	Solution so;
  93. 	cout<<"Output for arr1 is "<<so.getMaxProduct(arr1, sizeof(arr1)/sizeof(int))<<endl<<endl;
  94. 	cout<<"Output for arr2 is "<<so.getMaxProduct(arr2, sizeof(arr2)/sizeof(int))<<endl<<endl;
  95.  
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Output for arr1 is 720

Output for arr2 is 360
https://ideone.com/ul6Ypo
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!