【POJ】2559 Largest Rectangle in a Histogram

 1 #include<cstdio>
 2 #include<algorithm>
 3 typedef __int64 LL;
 4 #define MAXN 100010
 5 using namespace std;
 6 struct node
 7 {
 8     LL w,h;
 9 };
10 node st[MAXN];
11 int main()
12 {
13     LL ans,wide;
14     node temp;
15     int n,i,top;
16     while(scanf("%d",&n),n)
17     {
18         for(top=-1,ans=i=0;i<n;i++)
19         {
20             scanf("%I64d",&temp.h);
21             for(wide=0;top>-1&&st[top].h>=temp.h;top--)
22             {
23                 wide+=st[top].w;
24                 ans=max(ans,wide*st[top].h);
25             }
26             temp.w=wide+1;
27             st[++top]=temp;
28         }
29         for(wide=0;top>-1;top--)
30         {
31             wide+=st[top].w;
32             ans=max(ans,st[top].h*wide);
33         }
34         printf("%I64d\n",ans);
35     }
36     return 0;
37 }