can someone help me with this code I am getting a wrong answer while submitting but this passes the given test case.
I Have referred cp algorithms for this code . In cp- algorithms they have returned 0 if the maximum sum subarray is -ve. but i have changed it according to the given problem. Here is my solution
Thanks for the help in advance
#include<bits/stdc++.h>
using namespace std;
#define inf 50005
int n,m;
struct data {
int sum, pref, suff, ans;
};
int a[inf];
data t[4*inf];
data combine(data l, data r) {
data res;
res.sum = l.sum + r.sum;
res.pref = max(l.pref, l.sum + r.pref);
res.suff = max(r.suff, r.sum + l.suff);
res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
return res;
}
data make_data(int val) {
data res;
res.sum = val;
res.pref = res.suff = res.ans = max(INT_MIN, val);
return res;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = make_data(a[tl]);
} else {
int tm = (tl + tr) / 2;
build( v*2, tl, tm);
build( v*2+1, tm+1, tr);
t[v] = combine(t[v*2], t[v*2+1]);
}
}
data query(int v, int tl, int tr, int l, int r) {
if (l > r)
return make_data(0);
if(l==r) return make_data(a[l]);
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return combine(query(v*2, tl, tm, l, min(r, tm)),
query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
build(1,1,n);
while(m--)
{
int x,y;
cin>>x>>y;
data res=query(1,1,n,x,y);
cout<<res.ans<<endl;
}
}