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
     read(n);
     for i:=1 to n do read(a[i]);
end;

procedure add(node,l,r,x,val:longint);
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)
     else add(node shl 1+1,mid+1,r,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]);
     read(m);
     for i:=1 to m do
     begin
          read(x,y);
          find(1,1,n,x,y,ff,gg,hh,ss);
          writeln(ff);
     end;
end;

begin
     rf;
     pr;
end.

Code mẫu của ladpro98

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);
        readln(inp,n);
        for i:=1 to n do
                read(inp,a[i]);
        readln(inp);
        readln(inp,m);
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
                readln(inp,u,v);
                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
  Readln(fi, n);
  sum[0]:= 0;

  For i:= 1 to n do
    Begin
      Read(fi, a[i]);
      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
  Readln(fi, m);
  For i:= 1 to m do
    Begin
      Readln(fi, u, v);
      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;
}