Largest Rectangle in a Histogram

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=5*1e5+4;
 7 int ll[N],rr[N];
 8 int a[N];
 9 long long ans;
10 int n;
11 int main(){
12    while(~scanf("%d",&n)&&n){
13       memset(ll,0,sizeof(ll));
14       memset(rr,0,sizeof(rr));
15       memset(a,-1,sizeof(a));
16       for(int i=1;i<=n;i++)
17         scanf("%d",&a[i]);
18       for(int i=1;i<=n;i++){
19             ll[i]=i;
20             if(i==1)continue;
21           int t=i-1;
22          while(a[i]<=a[t]){
23             ll[i]=ll[t];
24             t=ll[t]-1;
25          }
26       }
27       for(int i=n;i>=1;i--){
28             rr[i]=i;
29             if(i==n)continue;
30           int t=i+1;
31          while(a[i]<=a[t]){
32             rr[i]=rr[t];
33             t=rr[t]+1;
34          }
35       }
36         ans=0;
37       for(int i=1;i<=n;i++)
38         ans=max(ans,(long long)(rr[i]-ll[i]+1)*(long long)a[i]);
39         printf("%I64d\n",ans);
40    }
41 }