fork download
copy 
  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;
  4. void largestAreaUnderHistogram(int arr[], int n){
  5.     stack<int>s;
  6.     int area,ans[100],st;
  7. for(int i=0;i<n;i++){
  8.     int curElement = arr[i];
  9.     if(s.empty()||arr[s.top()]<curElement){
  10.         s.push(i);
  11.     }
  12.     else{
  13.        st=s.top();
  14.        s.pop();
  15.     //comping areas
  16.         if(s.empty()){
  17.           area = arr[i]*i;
  18.         }
  19.         else{
  20.             area=arr[i]*(st-i+1);
  21.         }
  22.     }
  23.  
  24.     while(s.empty()==false){
  25.         st=s.top();
  26.         s.pop();
  27.     //comping areas
  28.         if(s.empty()){
  29.           area = arr[i]*i;
  30.         }
  31.         else{
  32.             area=arr[i]*(st-i+1);
  33.         }
  34.     }
  35.     ans[i] = area;
  36. }
  37. int Max=0;
  38. for(int i=0;i<n;i++){
  39.     cout<<ans[i]<<" ";
  40.     Max=max(Max,ans[i]);
  41. }
  42. cout<<"maxArea"<<Max;
  43. }
  44.  
  45. int main(){
  46. int arr[] = {6,2,5,4,5,1,6};
  47. int n= sizeof(arr)/sizeof(int);
  48. largestAreaUnderHistogram(arr,n);
  49. return 0;}
  50.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 2 10 12 20 5 36 maxArea36
https://ideone.com/qIXKGd
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!