游客 注册 | 登录
中文 | En

3037 - 良好的感觉

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

题目输入

第一行为 N(N <= 100000)，代表数据记录的天数。
第二行 N 个整数，代表每一天的感受值(每个数不超过 1000000)。

题目输出

一行，表示在最舒适的一段时间中的感受值。

输入/输出样例

输入格式

6
3 1 6 4 5 2

输出格式

60

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;
}
请先登陆