[单调栈]Max answer

佚名 6年前 (2019-04-21) 随笔 1112人围观抢沙发百度已收录

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input

First line contains an integer n(1 \le n \le 5 \times 10 ^5n(1≤n≤5×105).

Second line contains nn integers represent the array a (-10^5 \le a_i \le 10^5)a(−105≤ai≤105).

Output

One line contains an integer represent the answer of the array.

样例输入复制

5
1 2 3 4 5

样例输出复制

36

L[i]表示a[i]左边第一个比它小的数的位置，R[i]表示a[i]右边第一个比它小的数的位置(单调栈求出)
lmax[i]表示以i结尾的区间和最大的区间的左端点，rmax[i]表示以i开头的区间和最大的区间的右端点，lmin,rmin同理(递推求出)
以s[i]表示i的前缀和，则：
if(a[i]>=0) ans=max{ans,s[min(R[i]-1,rmax[i])]-s[max(L[i]+1,lmax[i])-1]};
else ans=max{ans,s[min(R[i]-1,rmin[i])]-s[max(L[i]+1),lmin[i])-1]};

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

ll a[500005],s[500005],L[500005],R[500005];
ll lmax[500005],rmax[500005],lmin[500005],rmin[500005];
struct Node{
  ll v,p;
}node[500005];
stack<Node> stk;

int main()
{
    ll n;scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    for(ll i=1;i<=n;i++){
        while(!stk.empty()) {if(stk.top().v>=a[i]) stk.pop();else break;}
        if(stk.empty()) L[i]=0;
        else L[i]=stk.top().p;
        stk.push(Node{a[i],i});
    }
    while(!stk.empty()) stk.pop();
    for(ll i=n;i>=1;i--){
        while(!stk.empty()) {if(stk.top().v>=a[i]) stk.pop();else break;}
        if(stk.empty()) R[i]=n+1;
        else R[i]=stk.top().p;
        stk.push(Node{a[i],i});
    }
    lmax[1]=1;
    for(ll i=2;i<=n;i++){
        ll tmp=s[i-1]-s[lmax[i-1]-1];
        if(tmp>0) lmax[i]=lmax[i-1];
        else lmax[i]=i;
    }
    rmax[n]=n;
    for(ll i=n-1;i>=1;i--){
        ll tmp=s[rmax[i+1]]-s[i];
        if(tmp>0) rmax[i]=rmax[i+1];
        else rmax[i]=i;
    }
    lmin[1]=1;
    for(ll i=2;i<=n;i++){
        ll tmp=s[i-1]-s[lmin[i-1]-1];
        if(tmp<0) lmin[i]=lmin[i-1];
        else lmin[i]=i;
    }
    rmin[n]=n;
    for(ll i=n-1;i>=1;i--){
        ll tmp=s[rmin[i+1]]-s[i];
        if(tmp<0) rmin[i]=rmin[i+1];
        else rmin[i]=i;
    }
    ll l,r,ans;
    if(a[1]>=0){
        l=max(L[1]+1,lmax[1]);
        r=min(R[1]-1,rmax[1]);
    }
    else{
        l=max(L[1]+1,lmin[1]);
        r=min(R[1]-1,rmin[1]);
    }
    ans=a[1]*(r-l+1);
    for(ll i=2;i<=n;i++){
        if(a[i]>=0){
            l=max(L[i]+1,lmax[i]);
            r=min(R[i]-1,rmax[i]);
        }
        else{
            l=max(L[i]+1,lmin[i]);
            r=min(R[i]-1,rmin[i]);
        }
        ans=max(ans,a[i]*(s[r]-s[l-1]));
    }
    printf("%lld\n",ans);
    return 0;
}