最长子段_牛客博客

$Description$
给定一个序列,找出最长的子段使得子段和大于 $0$ .

$Solution$
处理一个前缀和数组 $p$ ,假设合法区间为 $[l,r]$ ,即 $p_r-p_{l-1}>0$ ,题目就转化为求 $l,r \quad and \quad p_r-p_{l-1}>0$ .

解法一：线段树,将数组 $p$ 从小到大排序, $p[i]$ 相同按下标从大到小排序,每次维护一个最大值下标数组,将出现过的值删除,每次取出最大值即为所求的 $r$ .
解法二：单调栈,从头开始构造一个单调递减的数组,从后面往前扫,即答案中所求的 $l$ 一定会在这个单调栈中.

$Code$

线段树

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
template<typename T>int o(T x){cout<<x<<endl;return 0;}
int n;
pair<int,int>p[N];
int MAX[N*4];
int pos[N];
int main(){
  function<void(int l,int r,int rt)>
  build=[&](int l,int r,int rt){
      if(l==r){
          pos[MAX[rt]=l]=rt;return;
      }
      int mid=l+r>>1;
      build(l,mid,rt<<1);
      build(mid+1,r,rt<<1|1);
      MAX[rt]=max(MAX[rt<<1|1],MAX[rt<<1]);
  };
  function<void(int index)>
  up=[&](int index){
      int x=pos[index];
      MAX[x]=-1;
      while(x>1)MAX[x>>1]=max(MAX[x],MAX[x^1]),x>>=1;
  };
  cin>>n;
  for(int i=1;i<=n;i++){
      int x;
      scanf("%d",&x);
      p[i]={p[i-1].first+x,-i};
  }
  p[0]={0,0};
  sort(p,p+1+n);
  build(0,n,1);
  int ans=0;
  for(int i=0;i<=n;i++){
      int x=MAX[1];
      ans=max(ans,x+p[i].second);
      up(-p[i].second);
  }
  o(ans);
}

单调栈

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int p[N]={0};
int dp[N],Index[N];
int t=0;
int main(){
      int n;
      cin>>n;
      for(int i=1;i<=n;i++){
              int x;
              scanf("%d",&x);
              p[i]=p[i-1]+x;
      }
      for(int i=0;i<=n;i++){
              if(!t||dp[t]>p[i])dp[++t]=p[i],Index[t]=i;
      }
      int ans=0;
      for(int i=n;i>=1;i--){
              while(Index[t]>=i)t--;
              while(t>0&&p[i]-dp[t]>0)ans=max(ans,i-Index[t]),t--;
      }
      cout<<ans<<endl;
}