赞
踩
有N条的长条状的矩形,宽度都为1,第i条高度为Hi,相邻的竖立在x轴上,求最大的子矩形面积
求出当前点能够到达的最左边和最右边的位置,答案就是(最右边-最左边)*当前高度
ll l[maxn],r[maxn],a[maxn]; //l[i]记录i点能够到达最左边的位置 //r[i]记录i点能够到达最右边的位置 //最后答案就是(最右边-最左边+1)*a[i] int main(){ int n; while(~scanf("%d",&n)){ if(n==0)break; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } l[1]=1;r[n]=n; for(int i=2;i<=n;i++){ int tmp=i; while(tmp>=1&&a[i]<=a[tmp-1]){ tmp=l[tmp-1]; ///因为a[i]<=a[tmp-1],所以可以直接跳到tmp-1的l上 } l[i]=tmp; } for(int i=n-1;i>=1;i--){ int tmp=i; while(tmp<n&&a[i]<=a[tmp+1]){ tmp=r[tmp+1]; } r[i]=tmp; } ll maxx=-1; for(int i=1;i<=n;i++){ maxx=max(maxx,(r[i]-l[i]+1)*a[i]); } printf("%lld\n",maxx); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。