描述
kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 Ai，Ai 越大，表示人感觉越舒适。在一段时间 [i,j] 内，人的舒适程度定义为 [i,j] 中最不舒服的那一天的感受值 × [i,j]中每一天感受值的和。现在给出 kkk 在连续 N 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？
输入
第一行为 N，代表数据记录的天数。
第二行 N 个整数，代表每一天的感受值。
输出
一行，表示在最舒适的一段时间中的感受值。
#include <bits/stdc++.h> #define ll long long #define MAXN 100007 using namespace std; struct Point { int id,num; }sta[MAXN]; int n,tot; ll ans,sum[MAXN]; int a[MAXN],lef[MAXN],rig[MAXN]; inline int read() { int w=0,X=0; char ch=0; while (!isdigit(ch)) w|=ch=='-',ch=getchar(); while (isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } int main() { n=read(); for (int i=1;i<=n;i++) { a[i]=read(),sum[i]=sum[i-1]+a[i]; while (tot && sta[tot].num>=a[i]) rig[sta[tot--].id]=i; lef[i]=tot?sta[tot].id:0; sta[++tot]=(Point){i,a[i]}; } for (int i=1;i<=n;i++) { if (!rig[i]) rig[i]=n+1; ans=max(ans,a[i]*(sum[rig[i]-1]-sum[lef[i]])); } printf("%lld",ans); return 0; }