GSS - Đoạn con có tổng lớn nhất
Tác giả: RR
Ngôn ngữ: C++
#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);
}
}