Gym 101334F Feel Good

题意：
给定一串数，求一个区间，使得该区间的所有数之和乘以该区间内最小的数的乘积最大。

思路：
先预处理一下，计算出前缀和。

我们可以把每个点都当成该区间内最小的数，那么这个区间的最大长度就能延伸到左端和右端第一个比它小的数处。

这样一来，我们先计算出每个数左端和右端第一个比它小的数的坐标，最后遍历即可。

但是，求得时候还需要优化一下，如果在寻找的时候，碰到了比它大的数，那么直接移动到那个数所对应的比它小的数坐标，具体详见代码。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF=0x3f3f3f3f3f;
15 const int maxn=100000+5000;
16 
17 int n;
18 ll a[maxn];
19 ll sum[maxn];
20 ll L[maxn],R[maxn];
21 
22 int main()
23 {
24     freopen("feelgood.in","r",stdin);
25     freopen("feelgood.out","w",stdout);
26     //freopen("D:\input.txt","r",stdin);
27     while(~scanf("%d",&n))
28     {
29         sum[0]=0;
30         for(int i=1;i<=n;i++)
31         {
32             scanf("%lld",&a[i]);
33             sum[i]=sum[i-1]+a[i];
34         }
35 
36         int i,j;
37         for(i=1;i<=n;i++)
38         {
39             for(j=i-1;j>0;j--)
40             {
41                 if(a[j]<a[i])  {L[i]=j;break;}
42                 else if(a[j]>=a[i])  {j=L[j];j++;}
43             }
44             if(j==0)  L[i]=0;
45         }
46 
47         for(i=n;i>0;i--)
48         {
49             for(j=i+1;j<=n;j++)
50             {
51                 if(a[j]<a[i])  {R[i]=j;break;}
52                 else if(a[j]>=a[i])  {j=R[j];j--;}
53             }
54             if(j==n+1)  R[i]=n+1;
55         }
56 
57         ll ans=0;
58         int l,r;
59         for(int i=1;i<=n;i++)
60         {
61             ll temp=a[i]*(sum[R[i]-1]-sum[L[i]]);
62             if(ans<=temp)
63             {
64                 ans=temp;
65                 l=L[i]+1;
66                 r=R[i]-1;
67             }
68         }
69         printf("%lld
%d %d
",ans,l,r);
70     }
71 }