HU-156 Largest Rectanglen a Higogram

各板については、Area=height[i]*(j-k＋1)のうち、j<=x==k,height[x]==height[i];jを探して、kは肝心な点になって、普通の方法はきっとタイムアウトして、動的な計画を利用して、もしそれの左の高さはそれ自身に等しいならば、それの左側の左の境界はきっとこの性質を満たして、更にこの境界の左の繰り返しから下ります.   http://acm.hdu.edu.cn/showproblem.php?pid=1506 
           Larget Rectanglen a Higogram
Time Limit:2000/1000 MS(Java/Others)    メモリLimit:65536/32768 K(Java/Others)Total Submission(s):9550    Acceepted Submission(s):2633
Problem Description
A histogram is a polygon coposed of a sequence of rectangles aligned aa common base line.The rectangles have equal widths but may have different heights.Foxxample,the figure on the ft the shshshshshatototototoshshshshshshatotototoshshshshshshshshshshatotototototototoshshshshshshshshles s s shshshshshshshshshshshshshshshshshshshshshshshshshshshshshshshshshshshleles、the shshattttttis the width of the rectangles:Usually、histograms ares to represent discrete distrectantions、e.g.the frequencies of characters in texts.Note that the order of the rectangles、i.e.their heights、is import.Calculate the artlactorts the the the the the the lant the mont the the lactregles.too.The figure on the right shows the larget aligned rectangle for the depicted histogram.
 
Input
The input contains several test cases.Each test case describes a histogram and starts with a n integer n,denong the number of rectangles it is compsed of.You may asume that 1<=n=100000.The followe 1,The 1,The Ent Ent Ent stant.The 1)where 0<=hi==100000万.The numbers denote the heights of the rectangs of the the histogram in left-to-right order.The width of each rectangles 1.Aゼロfollows the input for the last test case.
 
Output
For each test case output on a single line the ara of the larget rectangle in the specified histogram.Remember this rectangle must be aligned at the common base line.
 
Sample Input
7 2 1 4 5 1 3
4,1000,000
0
 
Sample Output
8
4000

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int l[100010],r[100010];
int  a[100010];
int main()
{
	   int t,i;
	 long long  m,max;
	while(scanf("%d",&t)!=EOF&&t!=0)
	{
		max=0;
		memset(a,0,sizeof(a));
	   for(i=1;i<=t;i++)
	       scanf("%d",&a[i]);
	    for(i=1;i<=t;i++)
       {       l[i]=i;
           while(l[i]>1&&a[l[i]-1]>=a[i])
               l[i]=l[l[i]-1];
       }
       for(i=t;i>=1;i--)
       {
		   r[i]=i;
           while(r[i]<t&&a[r[i]+1]>=a[i])
               r[i]=r[r[i]+1];    
       }
	   for(i=1;i<=t;i++)
	   {
		   m=(long long)(r[i]-l[i]+1)*a[i];
		   if(max<m)
			  max=m;
	   }
	  cout<<max<<endl;
	}
	return 0;
}
//  4  1000000000  1000000000  1000000000  1000000000