话说这种相当于压缩路径的方法,我还是没怎么掌握!!!
#include<iostream> using namespace std; typedef long long ll; ll a[100005]; int main() { int left[100005],right[100005]; int n; while(scanf("%lld",&n),n!=0) { for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); left[i]=i; right[i]=i; } a[0]=a[n+1]=-1;//及其重要,我就因为这个反复超时因为如果a[2]=2,a[1]=1,进入下面的while循环回跑到a[0] for(int i=2;i<=n;i++) { while(a[left[i]-1]>=a[i]) left[i]=left[left[i]-1]; } for(int i=n-1;i>=1;i--) { while(a[right[i]+1]>=a[i]) right[i]=right[right[i]+1]; } ll max=0; for(int i=1;i<=n;i++) { ll t=a[i]*(right[i]-left[i]+1); if(t>max) max=t; } printf("%lld\n",max); } return 0; }