跑的还挺快的
先考虑朴素算法。处理出前缀和pre数组,双重循环枚举l,r,ans=max(ans,pre[r]-pre[l-1])
显然O(n^2)无法通过此题
我们调整一下循环逻辑

for(int j = 1;j<=n;j++){  
  for(int i = 1;i<=j;i++){  
    ans=max(ans,pre[j]-pre[i-1]);  
  }  
}

也就是固定右端点,枚举左端点。而每个位置的前缀和显然是固定的。那我们就将问转换成求[1,r-1]中的前缀最小值了
单调队列是一种特殊的队列，队列中的元素从队头到队尾是单调递减的。
具体来说：
队头（q[l]）的前缀和是队列中最大的。
队尾（q[r-1]）的前缀和是队列中最小的。
通过维护单调递减队列，我们可以在 O(1) 时间内找到 [1,j-1] 中的最小前缀和。
这样的话，我们在当前遍历到第i个元素时，只需要在队尾元素的前缀和大于pre[i]时一直弹出队尾元素，然后将i-1入队,就可以保证队列的单调性了。同时，队头元素是1~i-1中的前缀和最小值，pre[i]-pre[q[l]]也就是a[i]作为选取区间的最后一个元素时，所能得到的连续区间最大值
至此,我们将O(n^2)的时间复杂度降低至O(n),可以通过此题

#include <bits/stdc++.h>
#define ls p<<1
#define print pt
#define fi first
#define rs p<<1|1
#define se second
#define ins insert
#define getchar nc
#define pb push_back
#define lread rd<ll>
#define read rd<int>
#define mk make_pair
#define pf push_front
#define lowb(x) lower_bound(x)
#define uppb(x) upper_bound(x)
#define all(a) a.begin(),a.end()
#define lwb(a,b,c) lower_bound(a,b,c)
#define upb(a,b,c) upper_bound(a,b,c)
#define mset(x,a) memset(x,a,sizeof(x))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
using namespace std;
using ll = long long;
using i128 = __int128;
using ld = long double;
using pii = pair<int,int>;
using ull = unsigned long long;
using pll = pair<long long,long long>;
const int base = 1331;
const int N = 1e6 + 7;
const int M = 1e4 + 7;
const int mod = 1e9 + 7;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int dira[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
template <typename A, typename B>ostream &operator<<(ostream &os, const pair<A, B> &p){return os << '(' << p.first << ", " << p.second << ')';}
template<typename C,typename D = typename enable_if <!is_same<C, string>::value,typename C::value_type>::type>ostream &operator<<(ostream &os, const C &v){
    os << '{';string sep;for (const D &x : v)os << sep << x, sep = ", ";return os << '}';}
void dbg_out(){cerr << endl;}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T){cerr << ' ' << H;dbg_out(T...);}
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template<class T> T rd(){
    int f=0,c;T x=0;
    while(!isdigit(c=nc()))f|=c=='-';x=(c^48);
    while(isdigit(c=nc()))x=x*10+(c^48);if(f)x=-x;
    return x;
}
template<class T> void pt(T x,int c=-1){
    if(x<0)putchar('-'),x=-x;
    if(x>9)pt(x/10);putchar(x%10+48);
    if(c!=-1)putchar(c);
}
int n,m,pre[N];
int q[N],l,r;
int ans=-inf;
void solve(){
  n=read();
  rep(i,1,n)pre[i]=read();
  rep(i,1,n)pre[i]+=pre[i-1];
  rep(i,1,n){//因为计算时候使用的是前缀和，我们在队列中存储当前下标-1，方便调用前缀和计算
    while(l<r&&pre[i-1]<pre[q[r-1]])r--;
    q[r++]=i-1;
    ans=max(ans,pre[i]-pre[q[l]]);
  }
  print(ans);
  return ;
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//cout << fixed << setprecision(3);
//cout << right << left << setw(3);
//int _; _=read(); while(_--)
  solve();
  return 0;
}