fork download 
  1. #include<iostream>
  2. #include<stack>
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6.  
  7. long long int maxHistogramArea(vector<long long int> &a)
  8. {
  9.     stack<long long int> s;
  10.     long long int maxArea = 0;
  11.     int n = a.size();
  12.     for (int i = 0; i < n; i++)
  13.     {
  14.         if (s.empty())
  15.         {
  16.             s.push(i);
  17.         }
  18.         else
  19.         {
  20.             while (!s.empty() && a[i] < a[s.top()])
  21.             {
  22.                 long long int x = s.top();
  23.                 s.pop();
  24.                 long long int area = 0;
  25.                 if (s.empty())
  26.                     area = a[x] * i;
  27.                 else
  28.                     area = a[x] * (i - s.top() - 1);
  29.                 maxArea = max(area, maxArea);
  30.             }
  31.             s.push(i);
  32.         }
  33.     }
  34.     while (!s.empty())
  35.     {
  36.         long long int area = 0;
  37.         long long int x = s.top();
  38.         s.pop();
  39.         if (s.empty())
  40.         {
  41.             area = a[x] * n;
  42.         }
  43.         else
  44.         {
  45.             area = a[x] * (n - x);
  46.         }
  47.  
  48.         maxArea = max(area, maxArea);
  49.     }
  50.  
  51.     return maxArea;
  52. }
  53.  
  54. long long max(long long a, long long b){
  55.     return a>b?a:b;
  56. }
  57.  
  58. int main()
  59.  {
  60.  
  61.     long long testcases;
  62.     cin>>testcases;
  63.  
  64.     while(testcases--){
  65.  
  66.         stack<long long> s;
  67.  
  68.  
  69.         long long n;
  70.         cin>>n;
  71.  
  72.  
  73.         long long arr[n];
  74.         vector<long long int> a;
  75.  
  76.         for(long long i=0;i<n;i++)    
  77.         cin>>arr[i],a.push_back(arr[i]);
  78.  
  79.         cout<<maxHistogramArea(a)<<endl;
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.         }
  89.  
  90.  
  91.  
  92.  
  93. 	return 0;
  94. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin 
2
7
6 2 5 4 5 1 6
4
6 3 4 2
stdout 
12
9
https://ideone.com/sUAoFO
language:
C++14 (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!