大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
记录动态规划dpl，dpr，分辨记录i左面的比i大的，右面比i大的，然后(dpr[i]-dpl[i]+1)*h[i]得出长度
动态转移方程while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1]
/*************************************************************************
> File Name: hdu1506.cpp
> Author: yang
> Mail:826123027@qq.com
> Created Time: 2014年08月24日 星期日 23:41:16
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
#define N 100005
int main(){
int dpl[N],dpr[N];
long long h[N];
int n;
while(scanf("%d",&n),n){
for(int i=1;i<=n;i++)
scanf("%lld",&h[i]);
dpl[1]=1;
int temp;
for(int i=2;i<=n;i++){
temp=i;
while(temp>1 && h[temp-1]>=h[i]) temp=dpl[temp-1];
dpl[i]=temp;
}
dpr[n]=n;
for(int i=n-1;i>=1;i--){
temp=i;
while(temp<n && h[i]<=h[temp+1]) temp=dpr[temp+1];
dpr[i]=temp;
}
long long sum,ans=0;
for(int i=1;i<=n;i++){
// cout<<dpl[i]<<" "<<dpr[i]<<endl;
sum=(dpr[i]-dpl[i]+1)*h[i];
// cout<<"sum:"<<sum<<endl;
if(sum>ans) ans=sum;
}
cout<<ans<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118516.html原文链接：https://javaforall.net
