fork download 
  1.  
  2. // The main function to find the maximum rectangular  
  3. // area under given histogram with n bars 
  4. int getMaxArea(int hist[], int n) 
  5. { 
  6.     // Create an empty stack. The stack holds indexes  
  7.     // of hist[] array. The bars stored in stack are  
  8.     // always in increasing order of their heights. 
  9.     stack<int> s; 
  10.  
  11.     int max_area = 0; // Initialize max area 
  12.     int tp;  // To store top of stack 
  13.     int area_with_top; // To store area with top bar 
  14.                        // as the smallest bar 
  15.  
  16.     // Run through all bars of given histogram 
  17.     int i = 0; 
  18.     while (i < n) 
  19.     { 
  20.         // If this bar is higher than the bar on top  
  21.         // stack, push it to stack 
  22.         if (s.empty() || hist[s.top()] <= hist[i]) 
  23.             s.push(i++); 
  24.  
  25.         // If this bar is lower than top of stack,  
  26.         // then calculate area of rectangle with stack  
  27.         // top as the smallest (or minimum height) bar.  
  28.         // 'i' is 'right index' for the top and element  
  29.         // before top in stack is 'left index' 
  30.         else
  31.         { 
  32.             tp = s.top();  // store the top index 
  33.             s.pop();  // pop the top 
  34.  
  35.             // Calculate the area with hist[tp] stack  
  36.             // as smallest bar 
  37.             area_with_top = hist[tp] * (s.empty() ? i :  
  38.                                    i - s.top() - 1); 
  39.  
  40.             // update max area, if needed 
  41.             if (max_area < area_with_top) 
  42.                 max_area = area_with_top; 
  43.         } 
  44.     } 
  45.  
  46.     // Now pop the remaining bars from stack and calculate 
  47.     // area with every popped bar as the smallest bar 
  48.     while (s.empty() == false) 
  49.     { 
  50.         tp = s.top(); 
  51.         s.pop(); 
  52.         area_with_top = hist[tp] * (s.empty() ? i :  
  53.                                 i - s.top() - 1); 
  54.  
  55.         if (max_area < area_with_top) 
  56.             max_area = area_with_top; 
  57.     } 
  58.  
  59.     return max_area; 
  60. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function ‘int getMaxArea(int*, int)’:
prog.cpp:9:5: error: ‘stack’ was not declared in this scope
     stack<int> s;
     ^~~~~
prog.cpp:9:11: error: expected primary-expression before ‘int’
     stack<int> s;
           ^~~
prog.cpp:22:13: error: ‘s’ was not declared in this scope
         if (s.empty() || hist[s.top()] <= hist[i])
             ^
prog.cpp:48:12: error: ‘s’ was not declared in this scope
     while (s.empty() == false)
            ^
stdout 
Standard output is empty
https://ideone.com/qW14pK
language:
C++14 (gcc 8.3)
created:
6 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!