#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 105000
using namespace std;
typedef unsigned long long ULL;
struct number
{
	int x,j;
	number(){}
	number(int _x,int _j):x(_x),j(_j){}
} s[maxn];
int a[maxn];
int start[maxn],last[maxn];
ULL sum[maxn]={0};
ULL n;
void init()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	a[0]=a[n+1]=-1;
}
void make_start()
{
	int top=1;
	s[0]=number(-1,0);
	for (int i=1;i<=n+1;i++)
	{
		while (top>=1&&s[top].x>=a[i]) start[s[top].j]=s[top-1].j+1,--top;
		s[++top]=number(a[i],i);		
	}
}
void make_last()
{
	int top=1;
	s[0]=number(-1,0);
	for (int i=n;i>=0;i--)
	{
		while (top>=1&&s[top].x>=a[i]) last[s[top].j]=s[top-1].j-1,--top;
		s[++top]=number(a[i],i);		
	}
}
void solve()
{
	make_start();
	make_last();
	ULL ans=0,i,j;
	for (int k=1;k<=n;k++)
	{
		if (ans<=(sum[last[k]]-sum[start[k]-1])*a[k])
		{
			i=start[k],j=last[k];
			ans=(sum[j]-sum[i-1])*a[k];
		}
	}
	printf("%llu\n%llu %llu\n",ans,i,j);
}
int main()
{
	//freopen("c.txt","r",stdin);
	init();
	solve();
	return 0;
}

• Re:单调栈600MS飘过(为什么网上的大牛都是用DP+树状数组或者RMQ)~ (17) 2015329700043 2016-09-12 19:57:23