Here is my c++ code for GSS1:
#include <bits/stdc++.h>
using namespace std;
class SegmentTreeGSS1 {
public:
struct node{
long long sum;
long long maxSum;
long long prefixMaxSum;
long long suffixMaxSum;
node(long long a=0){
sum = maxSum = prefixMaxSum = suffixMaxSum = a;
}
void merge(node a, node b){
sum = a.sum + b.sum;
prefixMaxSum = max(a.prefixMaxSum, a.sum + b.prefixMaxSum);
suffixMaxSum = max(b.suffixMaxSum, b.sum + a.suffixMaxSum);
maxSum = max(a.suffixMaxSum+b.prefixMaxSum, max(prefixMaxSum, suffixMaxSum));
}
};
vector st;
vector array;
long long unsigned n;
long long unsigned left(long long unsigned node){
return node< right_limit || r < left_limit){
return node(INT_MIN);
};
if(l <= left_limit and r >= right_limit) return st[current_node];
long long mid = left_limit + (right_limit - left_limit)/2;
node left_node = max_sum_query(left(current_node), left_limit, mid, l, r);
node right_node = max_sum_query(right(current_node), mid + 1, right_limit, l, r);
if(left_node.maxSum == INT_MIN) return right_node;
if(right_node.maxSum == INT_MIN) return left_node;
node temp;
temp.merge(left_node, right_node);
return temp;
}
void build(long long unsigned current_node, long long unsigned low, long long unsigned high) {
if(low==high) {
st[current_node] = node(array[low]);
}
else{
long long unsigned mid = low + (high - low)/2;
build(left(current_node),low, mid);
build(right(current_node),mid + 1, high);
st[current_node].merge(st[left(current_node)], st[right(current_node)]);
}
}
long long unsigned max_sum_query(long long unsigned i, long long unsigned j){
return max_sum_query(1, 0, n - 1, i, j).maxSum;
}
SegmentTreeGSS1(const vector &a){
array = a;
n = a.size();
node temp(INT_MIN);
st.assign(n*4,temp);
build(1,0,n-1);
}
};
int main(){
long long int cases = 0;
scanf("%lld",&cases);
vector array;
while(cases--){
long long int num;
scanf("%lld",&num);
array.push_back(num);
}
SegmentTreeGSS1 *obj = new SegmentTreeGSS1(array);
scanf("%lld",&cases);
while(cases--){
long long int i,j;
scanf("%lld %lld",&i, &j);
printf("%lld\n",obj->max_sum_query(i-1,j-1));
}
return 0;
}
Please Help!