Max answer（单调栈+ST表）

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

Max answer

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

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

样例输出复制

题意：给定n个数，求区间最小值*区间和的值最大

思路：先求前缀和，然后用st表求出区间最大最小值，再用单调栈求出每个数的左右边界，然后枚举最小值和它的区间和即可

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 #define maxn 500005
 5 int n;
 6 ll sum[maxn],R[maxn],L[maxn],a[maxn],Max[maxn][25],Min[maxn][25];
 7 
 8 ll queryMax(int x,int y){
 9     int k=log2(y-x+1);
10     return max(Max[x][k],Max[y-(1<<k)+1][k]);
11 }
12 
13 ll queryMin(int x,int y){
14     int k=log2(y-x+1);
15     return min(Min[x][k],Min[y-(1<<k)+1][k]);
16 }
17 
18 int main(){
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++){
21         scanf("%lld",&a[i]);
22         sum[i]=sum[i-1]+a[i];
23         Max[i][0]=sum[i];
24         Min[i][0]=sum[i];
25     }
26     for(int i=1;i<25;i++){
27         for(int j=0;j+(1<<i)-1<=n;j++){
28             Max[j][i]=max(Max[j][i-1],Max[j+(1<<(i-1))][i-1]);
29             Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);
30         }
31     }
32 
33     stack<int>st;
34     for(int i=1;i<=n;i++){
35         while(!st.empty()&&a[i]<=a[st.top()]){
36             st.pop();
37         }
38         if(st.empty()){
39             L[i]=1;
40         }
41         else{
42             L[i]=st.top()+1;
43         }
44         st.push(i);
45     }
46     while(!st.empty()) st.pop();
47     for(int i=n;i>=1;i--){
48         while(!st.empty()&&a[i]<=a[st.top()]){
49             st.pop();
50         }
51         if(st.empty()){
52             R[i]=n;
53         }
54         else{
55             R[i]=st.top()-1;
56         }
57         st.push(i);
58     }
59     ll ans=-0x3f3f3f3f3f3f3f3f;
60     for(int i=1;i<=n;i++){
61         if(a[i]<0){
62             ll minr=queryMin(i,R[i]);
63             ll maxl=queryMax(L[i]-1,i);
64             ans=max(ans,(minr-maxl)*a[i]);
65         }
66         else if(a[i]>0){
67             ll maxr=queryMax(i,R[i]);
68             ll minl=queryMin(L[i]-1,i);
69             ans=max(ans,(maxr-minl)*a[i]);
70         }
71         else{
72             ans=max(ans,0LL);
73         }
74     }
75     printf("%lld\n",ans);
76 }