題意
給你一個(gè)序列，對(duì)于每個(gè)連續(xù)子區(qū)間，有一個(gè)價(jià)值，等與這個(gè)區(qū)間和×區(qū)間最小值，
求所有子區(qū)間的最大價(jià)值是多少。

?

分析：我們先用單調(diào)棧預(yù)處理 區(qū)間 [L[i] , R[i] ] 最小值為a[i] , 的L[i] , R[i] ;

首先我們明白 ， 如果a[i] >0 那 [L[i] , R[i] ] , 里面的數(shù)都是正數(shù) ， 所以應(yīng)該全選 ；

a[i] < 0 , 那我們?應(yīng)該在[L[i]-1 , i-1] 這里面找到前綴和最大 ， 在[i,R[i]] 這里找到前綴和最小

這樣的區(qū)間和才是最大

我。。。比賽的時(shí)候被自己秀死 ， 判斷a[i] >0 竟然也用了線段樹(shù)的做法 ， 導(dǎo)致邊界沒(méi)有控制好

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <queue>
#define MAXN 500001
#define inf 0x3f3f3f3f

using namespace std;
const int N=500001;
typedef long long ll;

int a[N],L[N],R[N],s[N],top;
ll sum[N],ans=-0x7f7f7f7f,n,h[N];
ll l=1,r=1;
struct node{
    int l,r;//區(qū)間[l,r]


    ll mx; //區(qū)間最大值
    ll mn; //區(qū)間最小值
}tree[MAXN<<2];//一定要開(kāi)到4倍多的空間

void pushup(int index){

    tree[index].mx = max(tree[index<<1].mx,tree[index<<1|1].mx);
    tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}

int cnt;
void build(int l,int r,int index){
    tree[index].l = l;
    tree[index].r = r;

    if(l == r){
       // scanf("%d",&tree[index].sum);
        tree[index].mn = tree[index].mx =sum[  cnt];
        return ;
    }
    int mid = (l r)>>1;
    build(l,mid,index<<1);
    build(mid 1,r,index<<1|1);
    pushup(index);
}

ll queryMIN(int l,int r,int index){
    if(l <= tree[index].l && r >= tree[index].r){
        //return tree[index].sum;

    return tree[index].mn;
    }

    int mid = (tree[index].l tree[index].r)>>1;


    ll Min =0x7f7f7f7f;
    if(l <= mid){

       // Max = max(query(l,r,index<<1),Max);
        Min = min(queryMIN(l,r,index<<1),Min);
    }
    if(r > mid){

      //  Max = max(query(l,r,index<<1|1),Max);
        Min = min(queryMIN(l,r,index<<1|1),Min);
    }
    //return ans;

    return Min;
    //return Min;
}
ll queryMAX(int l,int r,int index){
    if(l <= tree[index].l && r >= tree[index].r){
        //return tree[index].sum;
        return tree[index].mx;
        //return tree[index].mn;
    }

    int mid = (tree[index].l tree[index].r)>>1;

    ll Max = -0x7f7f7f7f;

    if(l <= mid){

        Max = max(queryMAX(l,r,index<<1),Max);
       // Min = min(query(l,r,index<<1),Min);
    }
    if(r > mid){

        Max = max(queryMAX(l,r,index<<1|1),Max);
        //Min = min(query(l,r,index<<1|1),Min);
    }
    //return ans;

    return Max;
    //return Min;
}
int main()
{


    ios::sync_with_stdio(false);
    cin>>n;
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i  )
    {
        cin>>a[i];
        sum[i]=sum[i-1] a[i];

    }
    build(1,n 1,1);



    top=0;
    for(int i=1;i<=n;i  )
    {
        while(top&&a[s[top]]>=a[i])
            --top;
        L[i]=(top==0?1:s[top] 1);
        s[  top]=i;
    }
    top=0;
    for(int i=n;i>=1;i--)
    {
        while(top&&a[s[top]]>=a[i])
            --top;
        R[i]=(top==0?n:s[top]-1);
        s[  top]=i;
    }
   // cout<<queryMIN(2,2,1)<<endl;
    for(int i=1;i<=n;i  )
    {
        ll temp;
        if(a[i]>0)
        {

       temp =(sum[R[i]] - sum[L[i]-1])*a[i];
//       cout<<L[i]<<" "<<R[i]<<endl;
//       cout<<queryMAX(i,R[i],1)<<" "<<queryMIN(L[i]-1,i-1,1)<<endl;
        }
        else if(a[i]<0)
        {

                if(L[i]==1 && queryMAX(max(1,L[i]-1),max(1,i-1),1)<0)
                    temp=(queryMIN(i,R[i],1))*a[i];
                else
                temp =(queryMIN(i,R[i],1)-queryMAX(max(1,L[i]-1),max(1,i-1),1))*a[i];

//       cout<<queryMAX(L[i]-1,i-1,1)<<" "<<queryMIN(i,R[i],1)<<endl;

        }
        else if(a[i]==0)
            temp=0;
//        else if(a[i]<0)
//        {
//            temp=(queryMIN(R[i],i,1) - queryMAX(L[i],i,1))*a[i];
//        }
        if(temp>ans) {ans=temp;}
    }

    cout<<ans<<endl;
}

?