发表于

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000+10;
const LL inf = 1e17;
int n;
int i,j;
LL sum[maxn],stmx[maxn][23],stmn[maxn][23];
int a[maxn],l[maxn],r[maxn];
stack<int> sta;
LL askmx(int l,int r){

    int k=log2(r-l+1);
    return max(stmx[l][k],stmx[r-(1<<k)+1][k]);
}
LL askmn(int l,int r){
    int k=log2(r-l+1);
    return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=n;i++) sum[i]=sum[i-1]+(LL)a[i];
    for (i=0;i<=n;i++) stmx[i][0]=stmn[i][0]=sum[i];
    for (j=1;(1<<j)<=n+1;j++){
        for (i=0;i+(1<<j)-1<=n;i++){
            stmx[i][j]=max(stmx[i][j-1],stmx[i+(1<<(j-1))][j-1]);
            stmn[i][j]=min(stmn[i][j-1],stmn[i+(1<<(j-1))][j-1]);
        }
    }
   
    for (i=1;i<=n;i++){
        while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
        if (sta.empty()) l[i]=1; else l[i]=sta.top()+1;
        sta.push(i);
    }
    while (!sta.empty()) sta.pop();
    for (i=n;i>=1;i--){
        while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
        if (sta.empty()) r[i]=n; else r[i]=sta.top()-1;
        sta.push(i);
    }
    LL ans=-inf;
    for (i=1;i<=n;i++){
        if (a[i]<0){
            LL R=askmn(i,r[i]);
            LL L=askmx(l[i]-1,i-1);
            ans=max(ans,(R-L)*(LL)a[i]);
        } 
        else if (a[i]>0){
            LL R=askmx(i,r[i]);
            LL L=askmn(l[i]-1,i-1);
            ans=max(ans,(R-L)*(LL)a[i]);
        } 
        else{
            ans=max(ans,0ll);
        }
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}