POJ2796 Feel Good【单调栈】

题目大意：

$n$n 个数，求某段区间的最小值 $\times$× 该段区间所有元素之和的最大值。

思路

在开头做一个前缀和，
然后往左和右扩展，
记录它在哪个区间内为最小值，
最后直接计算最小 $\times$× 总和有没有大于答案。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,ans,ansl=1,ansr=1,z[100010],qzh[100010];
struct node
{
	long long l,r,v;
}a[100010];
int main()
{
    cin>>n;
    for(long long i=1; i<=n; i++)
     {
     	scanf("%d",&a[i].v);
     	qzh[i]=qzh[i-1]+a[i].v;
        a[i].l=a[i].r=i;
     }
    long long tail=0;
    for(long long i=1; i<=n; i++)
     {
     	while(tail!=0&&a[i].v<=a[z[tail]].v)
     	 {
     	   a[i].l=a[z[tail]].l;
		   tail--;
     	 }
     	z[++tail]=i;
     }
    tail=0;
    for(long long i=n; i>=1; i--)
     {
     	while(tail!=0&&a[i].v<=a[z[tail]].v)
     	 {
     	   a[i].r=a[z[tail]].r;
		   tail--;
     	 }
     	z[++tail]=i;
     }
    for(long long i=1; i<=n; i++)
     if(a[i].v*(qzh[a[i].r]-qzh[a[i].l-1])>ans)
      {
       ans=a[i].v*(qzh[a[i].r]-qzh[a[i].l-1]);
       ansl=a[i].l,ansr=a[i].r;	
      }
    cout<<ans<<" "<<ansl<<" "<<ansr;
    return 0;
}