Feel Good

Feel Good
题面


题意
从一堆数中找到连续的一串数，假设有k个数，那么这一串数所代表的值就是这k个数的和乘上这个数中的最小值，所得的值记作maxn，问maxn最大是多少。

分析
这题可以首先记录一下前i个数的和（i属于1-n）,然后记录这n个数中每一个数作为最小值可以得到的最大值。然后搜索这n个数中的最大值并输出要求值。注意这道题如果用cin cout会出现tle而使用scanf和printf就可以通过了。

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
typedef struct{
	int left;
	int right;
	int val;
}P;
ll a[maxn],ma=-1,l,r;
P p[maxn];
int n,j;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i].val);
		a[i]=a[i-1]+p[i].val;
	}///a[i]储存的是前i项的和
	for(int i=1;i<=n;i++){
		j=i-1;
		while(1){
			if(p[i].val>p[j].val||j<=0){
				p[i].left=j+1;
	                        break;
			}
			else{
				j=p[j].left-1;
			}
		}
	}
	for(int i=n;i>=1;i--){
		j=i+1;
		while(1){
			if(p[i].val>p[j].val||j>=n+1){
				p[i].right=j-1;
	                        break;
			}
			else{
				j=p[j].right+1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		ll cn=p[i].val*(a[p[i].right]-a[p[i].left-1]);
		if(cn>ma){
			ma=cn;
			l=p[i].left;
			r=p[i].right;
		}
	}
	printf("%lld\n",ma);
	printf("%lld %lld\n",l,r);
    return 0;
}