hdu 1506 最大长方形 不错的DP

#include<stdio.h>
__int64 a[100005];
__int64 pre[100005];
__int64 next[100005];
int main()
{
__int64 n,i;
__int64 max,mid;
while(scanf("%I64d",&n))
{
if(n==0) return 0;
max=-1000000;
for(i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
next[i]=pre[i]=i;
}
for(i=0;i<n;i++)
{
while(pre[i]>0&&a[pre[i]-1]>=a[i])/*pre[i]>0 这个条件不要搞错 注意临界点是1 对于下面的式子0 没有意义*/
{
// pre[i]=pre[i]-1; // 这样会超时
pre[i]=pre[pre[i]-1];

}
}
for(i=n-2;i>=0;i--)
{
while(next[i]<n-1&&a[next[i]+1]>=a[i])
{
// next[i]=next[i]+1;
next[i]=next[next[i]+1];
}
}
for(i=0;i<n;i++)
{
mid=(__int64)(next[i]-pre[i]+1)*a[i];//中间过程的加法运算前面 必须要进行强制性类型转换 因为可能会相乘溢出
if(max<mid) max=mid;
}
printf("%I64d\n",max);
}
return 0;
}