这道题目就是向左向右遍历，找和他连续相邻并且大于它高度的，该题目卡时间，所以注意一下代码的那个while循环~~~，同时数据范围改为long long 型，要不然就会WA，再此我不知贡献了多少Submision了~~~呜呜呜呜，泪奔~~~
DP方程：ans=max((right[i]-left[i]+1)*height[i]);
#include<iostream> #include<stdio.h> #include<string> #include<string.h> #include<algorithm> using namespace std; int height[100005]; int LF[100005]; int RT[100005]; int N; int main() { while(scanf("%d",&N),N) { //录入数据 for(int i=1;i<=N;++i) scanf("%d",&height[i]); height[0]=height[N+1]=-1; //初始化LF,RT for(int i=1;i<=N;++i) LF[i]=RT[i]=i; //左边边界 for(int i=1;i<=N;++i) while(height[LF[i]-1]>=height[i]) LF[i]=LF[i]-1; //右边边界 for(int i=N;i>=1;--i) while(height[RT[i]+1]>=height[i]) RT[i]=RT[i]+1; long long ans=0; for(int i=1;i<=N;++i) { long long num=(RT[i]-LF[i]+1)*height[i]; ans=max(ans,num); } printf("%ld/n",ans); } return 0; }
