➤ Problem Link : GSS1
👉 Hint : Segment Tree
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct node
{
ll maxSum,sum,pref,suff;
};
typedef struct node NODE;
NODE st[4*500001];
ll arr[50001];
void build(int ind,int l,int r)
{
if(l==r)
{
st[ind].sum=st[ind].maxSum=arr[l];
st[ind].pref=st[ind].suff=arr[l];
return;
}
int m=(l+r)/2;
build(2*ind+1,l,m);
build(2*ind+2,m+1,r);
st[ind].sum=st[2*ind+1].sum+st[2*ind+2].sum;
st[ind].maxSum=max(st[2*ind+1].suff+st[2*ind+2].pref,max(st[2*ind+1].maxSum,st[2*ind+2].maxSum));
st[ind].pref=max(st[2*ind+1].pref,st[2*ind+1].sum+st[2*ind+2].pref);
st[ind].suff=max(st[2*ind+2].suff,st[2*ind+2].sum+st[2*ind+1].suff);
}
NODE query(int ind,int l,int r,int ql,int qr)
{
NODE n;
n.maxSum=n.sum=n.suff=n.pref=INT_MIN;
if(r<ql || l >qr)
return n;
if(ql<=l && qr>=r)
return st[ind];
int m=(l+r)/2;
NODE lc = query(2*ind+1,l,m,ql,qr);
NODE rc = query(2*ind+2,m+1,r,ql,qr);
n.maxSum=max(lc.suff+rc.pref,max(lc.maxSum,rc.maxSum));
n.sum=lc.sum+rc.sum;
n.pref=max(lc.pref,lc.sum+rc.pref);
n.suff=max(rc.suff,rc.sum+lc.suff);
return n;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,ql,qr;
cin>>n;
for(int i=1;i<<=n;i++)
cin>>arr[i];
build(1,1,n);
cin>>m;
while(m--)
{
cin>>ql>>qr;
NODE ans=query(1,1,n,ql,qr);
cout<<ans.maxSum<<endl;
}
}
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.