题解 P2422 【良好的感觉】

· · 题解

一道挺显然的单调栈题目。

我们可以找出这个以元素为最小值的极大区间，然后依次以每个元素为最小值更新出最优答案。

我们考虑如何找这个极大的区间，显然可以使用单调栈。

我们用单调栈求出左边第一个比当前元素i小的元素记作L_i，右边为R_i，于是我们可以再求一遍前缀和，最后这个元素对应的答案就是：(sum[R_i-1]-sum[L_i])\ * a_i.

预处理和计算都是线性的，跑的比较快。

Code: 
#include <bits/stdc++.h>

using namespace std;
typedef long long  ll;

const int N = 1e6 + 10;

ll a[N] , n;
ll st[N] , top;
ll L[N] , R[N];
ll sum[N];

int main () {
    scanf("%lld" , &n);
    for(int i = 1 ; i <= n ; i ++) scanf("%lld" , a + i);
    for(int i = 1 ; i <= n ; i ++) {
        while(top != 0 && a[st[top]] >= a[i]) {R[st[top]] = i;top --;}
        st[++ top] = i;
    }
    for(int i = 1 ; i <= top ; i ++) R[st[i]] = n + 1;
    top = 0;
    for(int i = n ; i >= 1 ; i --) {
        while(top != 0 && a[st[top]] >= a[i]) {L[st[top]] = i ; top --;}
        st[++ top] = i;
    }
    for(int i = 1 ; i <= top ; i ++) L[st[i]] = 0;
    ll ans = 0;
    for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + a[i];
    for(int i = 1 ; i <= n ; i ++) {
        ans = max(ans , a[i] * (sum[R[i] - 1] - sum[L[i]]));
    }
    printf("%lld\n" , ans);
    return 0;
}