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);
	}
}

Download