题意

给出数字序列，定义一个区间内的value值是这个区间所有数之和*这个区间的最小数，求对于这个数字序列，最大的value值

解题思路

和https://mp.csdn.net/postedit/89791878这个类似，找a[i]为最小值所在的区间，区间和用前缀和数组计算即可，再遍历i求最大的value值，注意数字序列中所有值都一样的情况

ac代码

数组比较大，要开在外面。。。

#include <iostream>
#include <algorithm>
#include <stack>
typedef long long ll;
#define maxn 1000005
using namespace std;
ll n,a[maxn]={0},sum[maxn]={0},l[maxn],r[maxn],L=-1,R=-1;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    stack<ll> s;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(ll i=1;i<=n;i++)
    {
        while(!s.empty() && a[s.top()]>=a[i])
            s.pop();
        if(s.empty()) l[i]=1;//注意此时l[i]的值
        else l[i]=s.top()+1;
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(ll i=n;i>=1;i--)
    {
        while(!s.empty() && a[s.top()]>=a[i])
            s.pop();
        if(s.empty()) r[i]=n;//注意此时r[i]的值
        else r[i]=s.top()-1;
        s.push(i);
    }
    ll ans=-1;
    for(ll i=1;i<=n;i++)
    {
        ll t=(sum[r[i]]-sum[l[i]-1])*a[i];
        if(t>ans)
        {
            ans=t;
            L=l[i];R=r[i];
        }
    }
    printf("%lld\n%lld %lld",ans,L,R);
    return 0;
}