原题链接：https://vjudge.net/problem/UVA-1619
分类：扫描法
备注：状态传递,细节
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll sum[maxn],a[maxn],L[maxn],R[maxn],ans,ansl,ansr;
int n,flg;
int main(void){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(~scanf("%d",&n)){if(flg)printf("\n");else flg=1; a[0]=a[n+1]=-1; for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],L[i]=R[i]=i;//左边这个数≥当前数，那么当前数的左边界必能扩展到左边这个数的左边界,右边界同理for(int i=1;i<=n;i++)while(a[L[i]-1]>=a[i])L[i]=L[L[i]-1];for(int i=n;i>=1;i--)while(a[R[i]+1]>=a[i])R[i]=R[R[i]+1];ans=a[1]*a[1]; ansl=ansr=1;for(int i=1;i<=n;i++){ll tmp=a[i]*(sum[R[i]]-sum[L[i]-1]);if(tmp>ans||(tmp==ans&&R-L>R[i]-L[i]))ans=tmp,ansl=L[i],ansr=R[i];}printf("%lld\n%lld %lld\n",ans,ansl,ansr);}return 0;
}