fork download 
  1. // C++ program to find maximum rectangular area in 
  2. // linear time 
  3. #include<bits/stdc++.h> 
  4. using namespace std; 
  5.  
  6. // The main function to find the maximum rectangular 
  7. // area under given histogram with n bars 
  8. int getMaxArea(int hist[], int n) 
  9. { 
  10. 	// Create an empty stack. The stack holds indexes 
  11. 	// of hist[] array. The bars stored in stack are 
  12. 	// always in increasing order of their heights. 
  13. 	stack<int> s; 
  14.  
  15. 	int max_area = 0; // Initialize max area 
  16. 	int tp; // To store top of stack 
  17. 	int area_with_top; // To store area with top bar 
  18. 					// as the smallest bar 
  19.  
  20. 	// Run through all bars of given histogram 
  21. 	int i = 0; 
  22. 	while (i < n) 
  23. 	{ 
  24. 		// If this bar is higher than the bar on top 
  25. 		// stack, push it to stack 
  26. 		if (s.empty() || hist[s.top()] <= hist[i]) 
  27. 			s.push(i++); 
  28.  
  29. 		// If this bar is lower than top of stack, 
  30. 		// then calculate area of rectangle with stack 
  31. 		// top as the smallest (or minimum height) bar. 
  32. 		// 'i' is 'right index' for the top and element 
  33. 		// before top in stack is 'left index' 
  34. 		else
  35. 		{ 
  36. 			tp = s.top(); // store the top index 
  37. 			s.pop(); // pop the top 
  38.  
  39. 			// Calculate the area with hist[tp] stack 
  40. 			// as smallest bar 
  41. 			area_with_top = hist[tp] * (s.empty() ? i : 
  42. 								i - s.top() - 1); 
  43.  
  44. 			// update max area, if needed 
  45. 			if (max_area < area_with_top) 
  46. 				max_area = area_with_top; 
  47. 		} 
  48. 	} 
  49.  
  50. 	// Now pop the remaining bars from stack and calculate 
  51. 	// area with every popped bar as the smallest bar 
  52. 	while (s.empty() == false) 
  53. 	{ 
  54. 		tp = s.top(); 
  55. 		s.pop(); 
  56. 		area_with_top = hist[tp] * (s.empty() ? i : 
  57. 								i - s.top() - 1); 
  58.  
  59. 		if (max_area < area_with_top) 
  60. 			max_area = area_with_top; 
  61. 	} 
  62.  
  63. 	return max_area; 
  64. } 
  65.  
  66. // Driver program to test above function 
  67. int main() 
  68. { 
  69. 	int hist[] = {6, 2, 5, 4, 5, 1, 6}; 
  70. 	int n = sizeof(hist)/sizeof(hist[0]); 
  71. 	cout << "Maximum area is " << getMaxArea(hist, n); 
  72. 	return 0; 
  73. } 
  74.  
Success #stdin #stdout 0s 4360KB
comments (?)
stdin 
Standard input is empty
stdout 
Maximum area is 12
https://ideone.com/aKUey0
language:
C++14 (gcc 8.3)
created:
5 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!