hdu 1506   Largest Rectangle in a Histogram

【题意】：给出一排建筑物的高度 其宽度均为1   求他们中最大的矩形面积

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define INF 10000000 7 using namespace std; 8  9 __int64 a[1000002],qian[1000002],hou[1000002],i,j,n,m,k;10 11 12 int main()13 {14     while(~scanf("%d",&n))15     {16         if(n==0)17             break;18         for(i=1;i<=n;i++)19            {
    21                scanf("%I64d",&a[i]);22                qian[i]=i;23                hou[i]=i;24            }25            for(i=2;i<=n;i++)26                while(qian[i]>1&&a[qian[i]-1]>=a[i])27                     qian[i]=qian[qian[i]-1];28            for(i=n;i>=1;i--)29                while(hou[i]
          
           =a[i])30 hou[i]=hou[hou[i]+1];31 __int64 ans=0;32 for(i=1;i<=n;i++)33 {34 __int64 temp;35 temp=(hou[i]-qian[i]+1)*a[i];36 if(ans