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