HDU 1506 Largest Rectangle in a Histogram
重点：从左到右，对于每个点，记算出他所能向左和向右延伸的最大边界
[cpp]
#include<stdio.h>
__int64 max,ans;
struct node
{
int l,r;
__int64 v;
}a[100010];
int main()
{
int i,n;
while(scanf("%d",&n)!=EOF&&n)
{
for(i=1;i<=n;i++)
{
scanf("%I64d",&a[i].v);
a[i].l=a[i].r=i;
}
a[0].v=a[n+1].v=-1;
for(i=1;i<=n;i++)
{
while(a[i].v<=a[a[i].l-1].v)//延伸左边界
{
a[i].l=a[a[i].l-1].l;
}
}
for(i=n;i>=1;i--)
{
while(a[i].v<=a[a[i].r+1].v)//延伸右边界
{
a[i].r=a[a[i].r+1].r;
}
}
max=0;
for(i=1;i<=n;i++)
{
ans=a[i].v*(a[i].r-a[i].l+1);
if(max<ans) max=ans;
}
printf("%I64d\n",max);
}
return 0;
}
补充：软件开发 , C++ ,
