luogu2659 美丽的序列

题目

luogu2659

代码#1

以每个数为最小值，向左右扫出区间，加一点小优化

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath> 
#define N 2000005
using namespace std;

int n,a[N],l[N],r[N];
long long ans;

int main()
{
	scanf("%d",&n);a[0]=a[n+1]=-1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(a[i]<=a[j-1])
		{
			if(!l[j]) j--;
			else j=l[j-1];
		}
		l[i]=j;
	}
	for(int i=n;i>=1;i--)
	{
		int j=i;
		while(a[i]<=a[j+1]) 
		{
			if(!r[j]) j++;
			else j=r[j+1];
		}
		r[i]=j;
	}
	for(int i=1;i<=n;i++) ans=max(ans,(long long)a[i]*(r[i]-l[i]+1));
	printf("%lld",ans);
	return 0;
}