## Editorial for Đoạn con có tổng lớn nhất

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

uses math;
const maxn=50010;
oo=1000000000;
var n,m:longint;
a:array[1..maxn] of longint;
f,g,h,s:array[1..maxn shl 2] of longint;

procedure rf;
var i:longint;
begin
for i:=1 to n do read(a[i]);
end;

var mid:longint;
begin
if (l=x) and (l=r) then
begin
f[node]:=val; g[node]:=val; h[node]:=val; s[node]:=val;
exit;
end;
mid:=(l+r) shr 1;
if x<=mid then add(node shl 1,l,mid,x,val)
f[node]:=max(f[node shl 1],max(f[node shl 1+1],h[node shl 1]+g[node shl 1+1]));
g[node]:=max(g[node shl 1],s[node shl 1]+g[node shl 1+1]);
h[node]:=max(h[node shl 1+1],s[node shl 1+1]+h[node shl 1]);
s[node]:=s[node shl 1]+s[node shl 1+1];
end;

procedure find(node,l,r,x,y:longint;var ff,gg,hh,ss:longint);
var mid,f1,f2,g1,g2,h1,h2,s1,s2:longint;
begin
if (l=x) and (r=y) then
begin
ff:=f[node]; gg:=g[node]; hh:=h[node]; ss:=s[node];
exit;
end;
mid:=(l+r) shr 1;
f1:=-oo; g1:=-oo; h1:=-oo; s1:=0;
f2:=-oo; g2:=-oo; h2:=-oo; s2:=0;
if y<=mid then
begin
find(node shl 1,l,mid,x,y,ff,gg,hh,ss);
exit;
end;
if x>mid then
begin
find(node shl 1+1,mid+1,r,x,y,ff,gg,hh,ss);
exit;
end;
find(node shl 1,l,mid,x,mid,f1,g1,h1,s1);
find(node shl 1+1,mid+1,r,mid+1,y,f2,g2,h2,s2);
ff:=max(f1,max(f2,h1+g2));
gg:=max(g1,s1+g2);
hh:=max(h2,s2+h1);
ss:=s1+s2;
end;

procedure pr;
var i,x,y,ff,gg,hh,ss:longint;
begin
for i:=1 to n do add(1,1,n,i,a[i]);
for i:=1 to m do
begin
find(1,1,n,x,y,ff,gg,hh,ss);
writeln(ff);
end;
end;

begin
rf;
pr;
end.


program gss;
uses    math;
type    node = record
lsum,rsum,sum,ans:longint;
end;
const   fi='';
maxN = 50010;

var     t:array[1..4*maxN] of node;
a:array[1..maxN] of longint;
m,n,i,u,v:longint;
inp:text;

procedure update(k,l,r,i:longint);
var     m,x,y:longint;
begin
if (l>i) or (r<i) then exit;
if l=r then
begin
t[k].lsum:=a[i];
t[k].rsum:=a[i];
t[k].sum:=a[i];
t[k].ans:=a[i];
exit;
end;

m:=(l+r) shr 1;
x:=k shl 1;
y:=x or 1;
update(x,l,m,i);
update(y,m+1,r,i);
t[k].lsum:=max(t[x].lsum,t[x].sum+t[y].lsum);
t[k].rsum:=max(t[y].rsum,t[y].sum+t[x].rsum);
t[k].sum:=t[x].sum+t[y].sum;
t[k].ans:=max(max(t[x].ans,t[y].ans),t[x].rsum+t[y].lsum);

end;

function query(k,l,r,i,j:longint):node;
var     m,x,y:longint;
left,right,res:node;
begin
if (l>=i) and (r<=j) then exit(t[k]);
m:=(l+r) shr 1;
x:=k shl 1;
y:=x or 1;
if m<i then exit(query(y,m+1,r,i,j));
if m>=j then exit(query(x,l,m,i,j));

begin
left:=query(x,l,m,i,j);
right:=query(y,m+1,r,i,j);
res.lsum:=max(left.lsum,left.sum+right.lsum);
res.rsum:=max(right.rsum,right.sum+left.rsum);
res.sum:=left.sum+right.sum;
res.ans:=max(max(left.ans,right.ans),left.rsum+right.lsum);
end;
exit(res);
end;

procedure input;
var     i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
end;

procedure init;
var     i:longint;
begin
for i:=1 to n do
update(1,1,n,i);
end;

begin
input;
init;
for i:=1 to m do
begin
writeln(query(1,1,n,u,v).ans);
end;
close(inp);
end.


#### Code mẫu của RR

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int NINF = -INF;

struct Node {
int minS, maxS, GSS;
Node() {minS = INF; maxS = NINF; GSS = NINF;}
Node(int _minS, int _maxS, int _GSS): minS(_minS), maxS(_maxS), GSS(_GSS) {}
};

Node combine(Node left, Node right) {
int _minS = min(left.minS, right.minS);
int _maxS = max(left.maxS, right.maxS);
int _GSS = NINF;
_GSS = max(_GSS, left.GSS);
_GSS = max(_GSS, right.GSS);
_GSS = max(_GSS, right.maxS - left.minS);
return Node(_minS, _maxS, _GSS);
}

int A[100010], S[100010];
Node node[200010];

void build(int i, int L, int R) {
if (L==R) {
int _GSS = max(NINF, A[L]);
node[i] = Node(S[L-1], S[L], _GSS);
return;
}

int middle = (L+R)/2;
build(2*i, L, middle);
build(2*i+1, middle+1, R);
node[i] = combine(node[2*i], node[2*i+1]);
return;
}

Node getNode(int i, int L, int R, int u, int v) {
if (u>R||v<L) return Node();
if (u<=L&&R<=v) return node[i];
int middle = (L+R)/2;
return combine(getNode(2*i, L, middle, u, v), getNode(2*i+1, middle+1, R, u, v));
}

int main() {
int n, m, u, v;
scanf("%d", &n);

for(int i=1; i<=n; i++) {
scanf("%d", &A[i]);
S[i]= S[i-1]+A[i];
}

build(1, 1, n);

scanf("%d", &m);
for(int i=1; i<=m; i++) {
scanf("%d %d", &u, &v);
Node res = getNode(1, 1, n, u, v);
printf("%d\n", res.GSS);
}
}


#### Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 50005
#define oo 1111111111
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

struct tree{
int m, M, gt;
tree(){};
tree(int _m, int _M,int _gt){m = _m, M = _M, gt = _gt;}
};

int n, a[maxn], m, x, y ;
tree T[maxn * 4];
tree empty = tree(oo,-oo,-oo);

tree merge(tree T1, tree T2){
tree res = tree(min(T1.m, T2.m), max(T1.M, T2.M),max(T1.gt, max(T2.gt, T2.M - T1.m)));
return res;
}

void init(int l, int r, int i){
if(l == r){
T[i].m = min(a[l], a[l - 1]);
T[i].M = a[l];
T[i].gt = a[l] - a[l - 1];
return ;
}
int mid = (l + r) / 2;
init(l, mid, i + i) ;
init(mid + 1, r, i + i + 1);
T[i] = merge(T[i + i], T[i + i + 1]);
// printf("%d %d %d %d %d %d\n",i,l,r,T[i].m,T[i].M,T[i].gt);
}

tree get(int l, int r, int i){
if(x > r || y < l) return empty;
if(x <= l && r <= y){ return T[i]; }
int mid = (l + r) / 2;
return merge(get(l, mid, i + i), get(mid + 1, r, i + i + 1));
}

int main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
scanf("%d",&n);
a[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
a[i] += a[i - 1];
}
init(1, n, 1);
scanf("%d",&m);
for(int i = 0; i < m; i++){
scanf("%d %d",&x,&y);
printf("%d\n",get(1, n, 1).gt);
}
}


#### Code mẫu của ll931110

{\$MODE DELPHI}
Program GSS2;
Uses math;
Const
input  = '';
output = '';
maxn = 50000;
maxv = 100000000000;
Type
rec = record
left,right,val: int64;
end;
Var
n,m,u,v: integer;
a,sum: array[0..maxn] of int64;
q: array[1..8 * maxn] of rec;
fi,fo: text;

Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);

Assign(fo, output);
Rewrite(fo);
End;

Procedure init;
Var
i: integer;
Begin
sum[0]:= 0;

For i:= 1 to n do
Begin
sum[i]:= sum[i - 1] + a[i];
End;
End;

Procedure build(i,low,high: integer);
Var
mid: integer;
Begin
If low = high then
Begin
q[i].left:= a[low];
q[i].right:= a[low];
q[i].val:= a[low];
exit;
End;

mid:= (low + high) div 2;
build(2 * i,low,mid);
build(2 * i + 1,mid + 1,high);

q[i].left:= max(q[2 * i].left,q[2 * i + 1].left + sum[mid] - sum[low - 1]);
q[i].right:= max(q[2 * i].right + sum[high] - sum[mid],q[2 * i + 1].right);

q[i].val:= max(q[2 * i].val,q[2 * i + 1].val);
q[i].val:= max(q[i].val,q[2 * i].right + q[2 * i + 1].left);
End;

Function calc(i,low,high: integer): rec;
Var
mid: integer;
x,y,t: rec;
Begin
t.left:= -maxv;
t.right:= -maxv;
t.val:= -maxv;

If (v < low) or (high < u) then exit(t);
If (u <= low) and (high <= v) then exit(q[i]);

mid:= (low + high) div 2;
x:= calc(2 * i,low,mid);
y:= calc(2 * i + 1,mid + 1,high);

t.left:= max(x.left,sum[mid] - sum[low - 1] + y.left);
t.right:= max(sum[high] - sum[mid] + x.right,y.right);

t.val:= max(x.val,y.val);
If t.val < x.right + y.left then t.val:= x.right + y.left;

calc:= t;
End;

Procedure solve;
Var
i: integer;
Begin
For i:= 1 to m do
Begin
Writeln(fo, calc(1,1,n).val);
End;
End;

Procedure closefile;
Begin
Close(fo);
Close(fi);
End;

Begin
openfile;
init;
build(1,1,n);
solve;
closefile;
End.


#### Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   50050
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class SegmentTree {
private:
struct Node {
static const int INF=(int)1e9+7;
int sum,left,right,all;
Node() {
sum=left=right=all=-INF;
}
Node(int x) {
sum=left=right=all=x;
}
bool isNULL(void) const {
return (all<=-INF);
}
Node operator + (const Node &x) const {
if (isNULL()) return (x);
if (x.isNULL()) return (*this);
Node res;
res.all=all+x.all;
res.left=max(left,all+x.left);
res.right=max(x.right,x.all+right);
res.sum=max(max(sum,x.sum),right+x.left);
return (res);
}
};
int n;
vector<Node> tree;
void build(int a[],int i,int l,int r) {
if (l>r) return;
if (l==r) tree[i]=Node(a[r]);
else {
int m=(l+r)>>1;
build(a,2*i,l,m);
build(a,2*i+1,m+1,r);
tree[i]=tree[2*i]+tree[2*i+1];
}
//printf("Tree %d (%d,%d): %d | %d | %d | %d\n",i,l,r,tree[i].all,tree[i].left,tree[i].right,tree[i].sum);
}
Node getMax(int i,int l,int r,int u,int v) const {
if (l>v || r<u || l>r || v<u) return (Node());
if (u<=l && r<=v) return (tree[i]);
int m=(l+r)>>1;
Node L=getMax(2*i,l,m,u,v);
Node R=getMax(2*i+1,m+1,r,u,v);
//printf("Get of %d (%d,%d): %d | %d |%d | %d\n",i,l,r,(L+R).all,(L+R).left,(L+R).right,(L+R).sum);
return (L+R);
}
public:
SegmentTree() {
n=0;
}
SegmentTree(int a[],int n) {
this->n=n;
tree.assign(4*n+7,Node());
build(a,1,1,n);
}
int getMax(int l,int r) const {
return (getMax(1,1,n,l,r).sum);
}
};
int a[MAX],n,q;
void init(void) {
scanf("%d",&n);
FOR(i,1,n) scanf("%d",&a[i]);
}
void process(void) {
SegmentTree myit(a,n);
scanf("%d",&q);
REP(zz,q) {
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",myit.getMax(l,r));
}
}
int main(void) {
init();
process();
return 0;
}


#### Code mẫu của khuc_tuan

/*
Bo khi, bai nay code Java, C# deo qua duoc Time Limit, danh code C++ tam vay
*/
#include "stdio.h"
#include "algorithm"

using namespace std;

#define Rep(i,n) for(int i=0,LLL=(n);i<LLL;++i)
#define For(i,a,n) for(int i=(a),LLL=(n);i<=LLL;++i)
#define Ford(i,a,n) for(int i=(a),LLL=(n);i>=LLL;--i)

struct INT {
int g, t, p, s;
};

int n, nd;
int a[50010], back[100], next[100];
INT Int[150010], ds[100];

void nhap(){
scanf("%d",&n);
For(i,1,n) scanf("%d",a+i);
}

void init(int node,int left,int right){
if(left==right) {
Int[node].g = a[left];
Int[node].t = a[left];
Int[node].p = a[left];
Int[node].s = a[left];
return;
}
int mid = (left+right)/2;
init( 2*node, left, mid);
init( 2*node+1, mid+1, right);
Int[node].s = Int[2*node].s + Int[2*node+1].s;
Int[node].t = max( Int[2*node].t, Int[2*node].s + Int[2*node+1].t);
Int[node].p = max( Int[2*node+1].p, Int[2*node+1].s + Int[2*node].p);
Int[node].g = max( Int[2*node].g, max( Int[2*node+1].g, Int[2*node].p + Int[2*node+1].t) );
}

void dfs(int node,int left,int right,int x,int y){
if(x<=left && right<=y){
ds[++nd] = Int[node] ;
return;
}
int mid = (left+right)/2;
if(x<=mid) dfs(2*node,left,mid,x,y);
if(mid<y) dfs(2*node+1,mid+1,right,x,y);
}

void qhd(){
int res=-2000000000;
back[1] = ds[1].p;
For(i,2,nd-1) back[i] = max( back[i-1] + ds[i].s, ds[i].p);
next[nd-1] = ds[nd].t;
Ford(i,nd-2,1) next[i] = max( next[i+1] + ds[i+1].s, ds[i+1].t);
For(i,1,nd-1) if(res<back[i]+next[i]) res = back[i]+next[i];
For(i,1,nd) if(res<ds[i].g) res = ds[i].g;
printf("%d\n",res);
}

void xuly(){
int m, x, y;
init(1,1,n);
scanf("%d",&m);
Rep(ttt,m) {
scanf("%d%d",&x,&y);
nd = 0;
dfs(1,1,n,x,y);
qhd();
}
}

int main(){
nhap();
xuly();
//    system("PAUSE");
return 0;
}