fork download
copy 
  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;
  4. void largestAreaUnderHistogram(long long int arr[], int n) {
  5.     stack<long long int>s;
  6.     long long int area = 0, ans[1000000002], st;
  7.     int i;
  8.     for (i = 0; i < n; i++) {
  9.         int curElement = arr[i];
  10.         if (s.empty() || arr[s.top()] <= curElement) {
  11.             s.push(i);
  12.         }
  13.         else {
  14.             while (!s.empty() && curElement < arr[s.top()]) {
  15.                 st=s.top();
  16.                 s.pop();
  17.                 //comping areas
  18.                 if (s.empty()) {
  19.                     area = arr[st] * i;
  20.                      ans[st] = area;
  21.                 }
  22.                 else {
  23.                     area = arr[st] * (i - s.top()-1);
  24.                     ans[st] = area;
  25.                 }
  26.             }
  27.             s.push(i);
  28.         }
  29.     }
  30.  
  31.     while (s.empty() == false) {
  32.         st=s.top();
  33.         s.pop();
  34.         //comping areas
  35.         if (s.empty()) {
  36.             area = arr[st] * i;
  37.             ans[st] = area;
  38.         }
  39.         else {
  40.             area = arr[st] * (i - s.top()-1);
  41.             ans[st] = area;
  42.         }
  43.  
  44.     }
  45.    long long int Max = 0;
  46.     for (int i = 0; i < n; i++) {
  47.         cout << ans[i] << " ";
  48.         Max = max(Max, ans[i]);
  49.     }
  50.     cout<<endl;
  51.     cout << "maxArea" << Max;
  52. }
  53.  
  54. int main() {
  55.     long long int arr[1000000002];
  56.     int n;
  57.     cin>>n;
  58.     int i=0;
  59.     while(i<n){
  60.         cin>>arr[i];
  61.         i++;
  62.     }
  63.     largestAreaUnderHistogram(arr, n);
  64.     return 0;
  65. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
5
1 2 3 4 5
stdout
copy 
5 8 9 8 5 
maxArea9
https://ideone.com/TPms6W
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!