1985.cpp

来自「自己的ac代码 在acm.zju.edu.cn 上的题目」· C++ 代码 · 共 45 行

#include<stdio.h>
int l[100005],r[100005],a[100005];
int main()
{
	int i,j,k;
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		for(i=1;i<=n;i++)
		{
			int left=i-1;
			while(left>0 && a[left]>=a[i])
			{
				left=l[left];
				left--;
			}
			l[i]=left+1;
		}
		for(j=n;j>=1;j--)
		{
			int right=j+1;
			while(right<=n && a[right]>=a[j])
			{
				right=r[right];
				right++;
			}
			r[j]=right-1;
		}
		long long maxn=0;
		for(i=1;i<=n;i++)
		{
			if((r[i]-l[i]+1)*(long long)a[i]>maxn)maxn=(r[i]-l[i]+1)*(long long)a[i];
		}
		printf("%lld\n",maxn);
	}
	return 0;
}