单调栈

 1 #include<cstdio>
 2 using namespace std;
 3 #define MAXN 111111
 4 int stack[MAXN];
 5 int l[MAXN],r[MAXN];
 6 long long a[MAXN],s[MAXN];
 7 int main(){
 8     int n;
 9     scanf("%d",&n);
10         for(int i=1; i<=n; ++i) scanf("%d",a+i),s[i]=s[i-1]+a[i];
11         a[++n]=-1;
12         int top=0;
13         for(int i=1; i<=n; ++i){
14             l[i]=r[i]=i;
15             while(top && a[stack[top]]>a[i]){
16                 l[i]=l[stack[top]];
17                 r[stack[top]]=i-1;
18                 --top;
19             }
20            // if(top && a[stack[top]]==a[i]) l[i]=l[stack[top]];
21             stack[++top]=i;
22         }
23         int x,y;
24         long long res=-1;
25         for(int i=1; i<n; ++i){
26             if(res<(s[r[i]]-s[l[i]-1])*a[i]){
27                 res=(s[r[i]]-s[l[i]-1])*a[i];
28                 x=l[i]; y=r[i];
29             }
30         }
31         printf("%lld
%d %d
",res,x,y);
32     
33     return 0;
34 }