Doubt in SPOJ problem (Segmented tree)

This is the link to the problem problem

and this is my solution . Plz help me in finding the error

``````#include<stdio.h>
int arr[50003];
int sum[600000];

#define max(a,b) a>b?a:b
int main()
{
int n,j,m,l,r; scanf("%d",&n);
for(j=0;j<n;j++)
{
scanf("%d",&arr[j]);
}
scanf("%d",&m);
while(m--)
{
scanf("%d %d",&l,&r); l--; r--;
}

seg_tree(arr,0,n-1,0);

int c= query(0,n-1,l,r,0);
printf("%d\n",c);
return 0;
}

int seg_tree(int *arr,int l,int r,int i)
{
if(l==r)
{
sum[i]=arr[l];
return arr[l];
}
else
{
int mid=(l+r)/2;
sum[2*i+1]=seg_tree(arr,l,mid,2*i+1);
sum[2*i+2]=seg_tree(arr,mid+1,r,2*i+2);

if(sum[2*i+1]<0 && sum[2*i+2] <0)
{
sum[i]= max(sum[2*i+1],sum[2*i+2]);
return sum[i];
}

else if(sum[2*i+1]<0)
{
sum[i]= sum[2*i+2];
return sum[i] ;
}

else if(sum[2*i+2]<0)
{sum[i]= sum[2*i+1];
return sum[i] ;
}

else
{
sum[i]= sum[2*i+1]+sum[2*i+2];
return sum[i];
}
}

}

int query(int a,int b,int i,int j,int node)
{
if(a>j || b<i) return -16000;

else if(a>=i && b<=j)
return sum[node];
else
{
int mid=(a+b)/2;
int l=query(a,mid,i,j,2*node+1);
int r=query(mid+1,b,i,j,2*node+2);

if(l<0 && r <0)
{
return max(l,r);
}

else if(l<0)
{
return r;
}

else if(r<0)
{return l;
}

else
{
return (l+r);
}
}

}``````

For starters

5
3 -10 100 -2 20
1
1 5

Answer : 118 : your output 123

@akasareen , i think i didn’t understand the question wrong…!
what exactly is it asking in the question, can you plz tell ??

Shouldn’t you be returning 0 if the required query is having a no overlap instead of a big negative number ?

@valts7_100 actually the question is asking you to compute the maximum sum over a range in array.

Actually to solve this you have to use this technique-

we need to store 4 values in each segment tree node to be able to merge child nodes to form a solution to their parent’s node:

1)Maximum sum of a subarray, starting at the leftmost index of this range

2)Maximum sum of a subarray, ending at the rightmost index of this range

3)Maximum sum of any subarray in this range

4)Sum of all elements in this range

``````sum = left.sum + right.sum;
prefixMaxSum = max(left.prefixMaxSum, left.sum + right.prefixMaxSum);
suffixMaxSum = max(right.suffixMaxSum, right.sum + left.suffixMaxSum);
maxSum = max(prefixMaxSum, max(suffixMaxSum, max(left.maxSum, max(right.maxSum, left.suffixMaxSum +     right.prefixMaxSum))));
``````

Try again , ask me if any problem persists I will be happy to help you.

2 Likes
//