3037 - 良好的感觉
jyy 做了一个人体感觉分析器。每一天，人都有一个感受值 Ai，Ai 越大，表示人感觉越舒适。在一段时间[i, j]内，人的舒适程度定义为[i, j]中最不舒服的那一天的感受值 * [i,j]中每一天感受值的和。现在给出 jyy 在连续 N 天中的感受值，请问，在哪一段时间，jyy感觉最舒适？
Input
第一行为 N(N <= 100000)，代表数据记录的天数。
第二行 N 个整数，代表每一天的感受值(每个数不超过 1000000)。
Output
一行，表示在最舒适的一段时间中的感受值。
Examples
Input
6 3 1 6 4 5 2
Output
60
Solution C++
#include <cstdio> #include <iostream> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <deque> using namespace std ; int n,i,j,l,r,a[100002],q[100002],ll[100002],rr[100002]; long long maxn,s[100002]; int main() { //freopen("feelgood.in","r",stdin); //freopen("feelgood.out","w",stdout); cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } l=1;r=0; memset(ll,0,sizeof(ll)); memset(rr,0,sizeof(rr)); memset(q,0,sizeof(q)); for(i=1;i<=n+1;i++) { while(a[i]<a[q[r]]&&l<=r) rr[q[r--]]=i-1; q[++r]=i; } l=1;r=0; memset(q,0,sizeof(q)); for(i=n;i>=0;i--) { while(a[i]<a[q[r]]&&l<=r) ll[q[r--]]=i+1; q[++r]=i; } maxn=0; for(i=1;i<=n;i++) if((s[rr[i]]-s[ll[i]-1])*a[i]>maxn) maxn=(s[rr[i]]-s[ll[i]-1])*a[i]; cout<<maxn; }