Max answer 计蒜客

https://nanti.jisuanke.com/t/38228

单调栈找出每个数的单调区间[ lef[i], rgt[i] ]

如果ary[i]>0 在[ lef[i]-1, i-1 ]内找一最小前缀和 在[ i,rgt[i] ]内找一最大前缀和

如果ary[i]<0(这个情况一开始居然忽略掉了 太傻吊) 在[ lef[i]-1, i-1 ]内找一最大前缀和 在[ i,rgt[i] ]内找一最小前缀和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=0x3f3f3f3f3f3f3f3f;
const int maxn=5e5+10;

stack <int> stk;
ll minn[4*maxn],maxx[4*maxn];
ll ary[maxn],sum[maxn];
int lef[maxn],rgt[maxn];
int n;

void init()
{
    int i;
    for(i=1;i<=n;i++){
        while(!stk.empty()&&ary[stk.top()]>=ary[i]) stk.pop();
        if(stk.empty()) lef[i]=1;
        else lef[i]=stk.top()+1;
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();
    for(i=n;i>=1;i--){
        while(!stk.empty()&&ary[stk.top()]>=ary[i]) stk.pop();
        if(stk.empty()) rgt[i]=n;
        else rgt[i]=stk.top()-1;
        stk.push(i);
    }
}

void pushup(int cur)
{
    minn[cur]=min(minn[2*cur],minn[2*cur+1]);
    maxx[cur]=max(maxx[2*cur],maxx[2*cur+1]);
}

void build(int l,int r,int cur)
{
    int m;
    if(l==r){
        minn[cur]=sum[l],maxx[cur]=sum[l];
        return;
    }
    m=(l+r)/2;
    build(l,m,2*cur);
    build(m+1,r,2*cur+1);
    pushup(cur);
}

ll query(int tp,int pl,int pr,int l,int r,int cur)
{
    ll res;
    int m;
    if(pl<=l&&r<=pr){
        if(tp==0) return minn[cur];
        else return maxx[cur];
    }
    if(tp==0){
        res=N,m=(l+r)/2;
        if(pl<=m) res=min(res,query(tp,pl,pr,l,m,2*cur));
        if(pr>m) res=min(res,query(tp,pl,pr,m+1,r,2*cur+1));
    }
    else{
        res=-N,m=(l+r)/2;
        if(pl<=m) res=max(res,query(tp,pl,pr,l,m,2*cur));
        if(pr>m) res=max(res,query(tp,pl,pr,m+1,r,2*cur+1));
    }
    return res;
}

int main()
{
    ll ans,val1,val2;
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&ary[i]);
        sum[i]=sum[i-1]+ary[i];
    }
    init();
    build(0,n,1);
    ans=-N;
    for(i=1;i<=n;i++){
        if(ary[i]>0){
            val1=query(0,lef[i]-1,i-1,0,n,1);
            val2=query(1,i,rgt[i],0,n,1);
            ans=max(ans,(val2-val1)*ary[i]);
        }
        else{
            val1=query(1,lef[i]-1,i-1,0,n,1);
            val2=query(0,i,rgt[i],0,n,1);
            ans=max(ans,(val2-val1)*ary[i]);
        }
    }
    printf("%lld\n",max(ans,0ll));
    return 0;
}