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. :slight_smile:

2 Likes
//