hdu 1506 Largest Rectangle in a Histogram

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 200000
 5 #define ll __int64
 6 using namespace std;
 7 
 8 int n;
 9 ll a[maxn];
10 ll l[maxn],r[maxn];
11 
12 int main()
13 {
14     while(scanf("%d",&n)!=EOF)
15     {
16         if(n==0) break;
17         for(int i=1; i<=n; i++)
18         {
19             scanf("%I64d",&a[i]);
20             l[i]=i;
21             r[i]=i;
22         }
23         a[0]=a[n+1]=-1;
24         for(int i=1; i<=n; i++)
25         {
26             while(a[i]<=a[l[i]-1]) l[i]=l[l[i]-1];
27         }
28         for(int i=n; i>=1; i--)
29         {
30             while(a[i]<=a[r[i]+1]) r[i]=r[r[i]+1];
31         }
32         ll max1=0;
33         for(int i=1; i<=n; i++)
34         {
35             max1=max(max1,a[i]*(r[i]-l[i]+1));
36         }
37         printf("%I64d\n",max1);
38     }
39     return 0;
40 }