Max answer

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.

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

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

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

 

 

用单调栈判断以每个值为最小值的最大左边界和右边界。后对对每个值分成负数和正数讨 论取可行区间内的最小或最大值，方法为求前缀和和后缀和，然后用线段树求区间最值。

 

代码:

  1 //I-线段树+单调栈
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn=5e5+10;
  6 const int inf=0x3f3f3f3f;
  7 
  8 #define lson l,m,rt<<1
  9 #define rson m+1,r,rt<<1|1
 10 
 11 int a[maxn],l[maxn],r[maxn];
 12 ll pre[maxn],beh[maxn],maxl[maxn<<2],minl[maxn<<2],maxr[maxn<<2],minr[maxn<<2];
 13 
 14 void pushup(int rt)
 15 {
 16     maxl[rt]=max(maxl[rt<<1],maxl[rt<<1|1]);
 17     minl[rt]=min(minl[rt<<1],minl[rt<<1|1]);
 18     maxr[rt]=max(maxr[rt<<1],maxr[rt<<1|1]);
 19     minr[rt]=min(minr[rt<<1],minr[rt<<1|1]);
 20 }
 21 
 22 void build(int l,int r,int rt)
 23 {
 24     if(l==r){
 25         maxl[rt]=minl[rt]=beh[l];
 26         maxr[rt]=minr[rt]=pre[l];
 27         return ;
 28     }
 29 
 30     int m=(l+r)>>1;
 31     build(lson);
 32     build(rson);
 33     pushup(rt);
 34 }
 35 
 36 ll query(int op,int L,int R,int l,int r,int rt)
 37 {
 38     if(L<=l&&r<=R){
 39         if     (op==1) return maxl[rt];
 40         else if(op==2) return minl[rt];
 41         else if(op==3) return maxr[rt];
 42         else if(op==4) return minr[rt];
 43     }
 44 
 45     int m=(l+r)>>1;
 46     ll ret;
 47     if(op==1||op==3){
 48         ret=-inf;
 49         if(L<=m) ret=max(ret,query(op,L,R,lson));
 50         if(R> m) ret=max(ret,query(op,L,R,rson));
 51     }
 52     else if(op==2||op==4){
 53         ret=inf;
 54         if(L<=m) ret=min(ret,query(op,L,R,lson));
 55         if(R> m) ret=min(ret,query(op,L,R,rson));
 56     }
 57     return ret;
 58 }
 59 
 60 deque<int> deq;//因为是双端队列，所以插的时候要插到头上才能实现栈的功能
 61 
 62 int main()
 63 {
 64     int n;
 65     scanf("%d",&n);
 66     for(int i=1;i<=n;i++){
 67         scanf("%d",&a[i]);
 68     }
 69     for(int i=1;i<=n;i++){
 70         pre[i]=pre[i-1]+a[i];
 71     }
 72     for(int i=n;i>=1;i--){
 73         beh[i]=beh[i+1]+a[i];
 74     }
 75     build(1,n,1);
 76     for(int i=1;i<=n;i++){
 77         while(deq.size()&&a[deq.front()]>=a[i]) deq.pop_front();
 78         if(deq.empty()) l[i]=1;
 79         else l[i]=deq.front()+1;
 80         deq.push_front(i);
 81     }
 82     deq.clear();
 83     for(int i=n;i>=1;i--){
 84         while(deq.size()&&a[deq.front()]>=a[i]) deq.pop_front();
 85         if(deq.empty()) r[i]=n;
 86         else r[i]=deq.front()-1;
 87         deq.push_front(i);
 88     }
 89     ll maxx=-inf,ret;
 90     for(int i=1;i<=n;i++){
 91         if(a[i]>=0){
 92             ret=query(1,l[i],i,1,n,1);
 93             ret+=query(3,i,r[i],1,n,1);
 94             ret=ret-beh[i]-pre[i]+a[i];
 95             ret*=a[i];
 96 //            cout<<query(1,l[i],i,1,n,1)<<" "<<query(3,i,r[i],1,n,1)<<endl;
 97         }
 98         else{
 99             ret=query(2,l[i],i,1,n,1);
100             ret+=query(4,i,r[i],1,n,1);
101             ret=ret-beh[i]-pre[i]+a[i];
102             ret*=a[i];
103         }
104         maxx=max(maxx,ret);
105     }
106     printf("%lld\n",maxx);
107 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄