(CF1691D) Max GEQ Sum

一.题意：

给你一串数，要求你判断是不是这串数的每一个子区间都满足，这个区间内所有数字的和大于这个区间的最大数字。

二.思路：

以每个最大值为中心，分别求能够向左向右延申到的区间的一个和（不包括此最大值），如果这个和出现比0大的情况，那就是不满足。

利用了栈。

这里以向左延申为例，从1~n遍历这串数，并把这串数中每一个数加入栈中（作为区间的的左边界），当发现当前遍历的数字（假设为区间的右边界（也是当前区间最大数））大于他左边刚刚加入栈的数字（栈顶元素）的时候，那么这个栈顶元素就可以作为它的左边界，然后用前缀和来求这段【栈顶元素~当前遍历的数字】区间和（和不包括当前遍历的这个数），若这段和>0（加上右边界肯定是大于这个右边界（当前区间最大数）了），则不满足，然后将栈顶元素弹出，继续试着向左延申区间（新栈顶元素和当前这个数进行比较），如此循环，直到当前栈顶元素大于当前这个数为止，此时当前这个数已经往左延申到最大了，接着把这个数加入栈中作为一个准左边界，然后接着遍历，假设当前的数为区间最大数看看能不能向左延申，能的话再算一个和（此时我们可以发现少了很多个准左边界，因为之前这些边界已经作为左边界算了一次，而那段区间和肯定<0，所以不用担心，<0的数不会使得区间和变大，因此跳过这些数接着往左找左边界就行）

向右延申同理。

只要以区间最大值为右/左边界向左延申或者向右延申的区间和都<0的话，那么这个数字也不作为左右边界的时候肯定是满足条件的。

三.代码

//单调栈做法
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stack>
using namespace std;
const int N = 2e5+10;
typedef struct aa
{
    int w;
    int pos;
}node;
node v[N];
typedef long long LL;

LL suml[N],sumr[N];
stack<node> p;
void solve()
{
    int n;
    cin>>n;
    
    suml[0]=0;
    for(int i=1;i<=n;i++) cin>>v[i].w,v[i].pos=i,suml[i]=suml[i-1]+v[i].w;
    
    sumr[n+1]=0;
    for(int i=n;i>=1;i--) sumr[i]=sumr[i+1]+v[i].w;
    
    while(!p.empty())
    p.pop();
    
    LL maxv=-1e15;
    bool flag=0;
    for(int i=1;i<=n;i++)//向右延申区间
    {
        while(!p.empty()&&p.top().w<=v[i].w)
        {
            int poss=p.top().pos;
            maxv=max(maxv,suml[i-1]-suml[poss-1]);
            p.pop();
        }
        
        if(maxv>0)
        {
            flag=1;
            break;
        }
        p.push({v[i]});
    }
    if(flag)
    {
        puts("NO");
        return;
    }
    while(!p.empty()) p.pop();
    for(int i=n;i>=1;i--)//向左延申区间
    {
        while(!p.empty()&&p.top().w<=v[i].w)
        {
            int poss=p.top().pos;
            maxv=max(maxv,sumr[i+1]-sumr[poss+1]);
            p.pop();
        }
        if(maxv>0)
        {
            flag=1;
            break;
        }
        p.push({v[i]});
    }
    if(flag)
    {
        puts("NO");
        return;
    }
    puts("YES");
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}