洛谷 P2422：良好的感觉 ← 单调队列+前缀和

【题目来源】
https://www.luogu.com.cn/problem/P2422

【题目描述】
kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 Ai，Ai 越大，表示人感觉越舒适。在一段时间 [i,j] 内，人的舒适程度定义为 [i,j] 中最不舒服的那一天的感受值 × [i,j] 中每一天感受值的和。现在给出 kkk 在连续 N 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

【输入格式】
第一行为 N，代表数据记录的天数。
第二行 N 个整数，代表每一天的感受值。

【输出格式】
一行，表示在最舒适的一段时间中的感受值。

【输入样例】
6
3 1 6 4 5 2

【输出样例】
60

【说明/提示】
kkk 最开心的一段时间是第 3 天到第 5 天，开心值：(6+4+5)×4=60。
对于 30% 的数据，1≤N≤100。
对于 70% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤100000，1≤感受值≤1000000。

【算法分析】
单调队列+前缀和。
● 单调队列：https://blog.csdn.net/hnjzsyjyj/article/details/144603573
● 前缀和：https://blog.csdn.net/hnjzsyjyj/article/details/144635240

【算法代码】

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

typedef long long LL;
const int maxn=1e5+5;
LL a[maxn], le[maxn], q[maxn], sum[maxn];
LL ans,t=0;

int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    a[++n]=0;

    for(int i=1; i<=n; i++) {
        sum[i]=sum[i-1]+a[i];
        while(a[i]<a[q[t]]) {
            le[q[t]]+=(sum[i-1]-sum[q[t]]);
            t--;
        }
        le[i]=sum[i]-sum[q[t]];
        q[++t]=i;
    }

    for(int i=1; i<=n; i++) ans=max(ans,le[i]*a[i]);
    cout<<ans<<endl;

    return 0;
}

/*
in:
6
3 1 6 4 5 2

out:
60
*/

【参考文献】
https://www.cnblogs.com/Hamine/p/15229237.html
https://www.cnblogs.com/acioi/p/11688089.html
https://www.cnblogs.com/acioi/p/11677694.html