Help in Segment tree maximum query

This is a simple question to find maximum between a given range in array.
Please help.

Question link - https://www.spoj.com/problems/GSS1/
My solution ->
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {

public static void maketree(int index, int start, int end, int arr[], int tree[]){
    
    if(start == end){
        tree[index] = arr[start];
    }
    else{
        int mid = start+(end-start)/2;
        maketree((2*index)+1, start, mid, arr, tree);
        maketree((2*index)+2, mid+1, end, arr, tree);
        int v1 = tree[(2*index)+1];
        int v2 = tree[(2*index)+2];
        tree[index] = (int)Math.max(v1, v2);
    }
    
}


public static void update(int index,int start, int end, int pos, int value,int arr[], int tree[]){
    
    if(start == end){
        arr[pos] = value;
        tree[index] = value;
    }
    else{
        
        int mid = start+(end-start)/2;;
        if(pos>=start && pos<=mid){
            update((2*index)+1, start, mid, pos, value, arr, tree);
        }
        else{
            update((2*index)+2, mid+1, end, pos, value, arr, tree);
        }
        
        int v1 = tree[(2*index)+1];
        int v2 = tree[(2*index)+2];
        tree[index] = (int)Math.max(v1, v2);
        
    }
    

}

public static int query(int index, int start, int end, int l, int r, int tree[]){
    
    if(l>end || r<start)
        return Integer.MIN_VALUE;
    else if(l<=start && r>=end)
        return tree[index];
    else{
        
        int mid = start + (end-start)/2;
        int v1 = query((2*index)+1, start, mid, l, r,tree);
        int v2 = query((2*index)+2, mid+1, end, l, r, tree);
        return (int)Math.max(v1,v2);
                    
    }
        
}



public static void main(String args[] ) throws Exception {
   
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine().trim());
    int arr[] = new int[n];
    int tree[] = new int[(4*n)+2];
    String s[] = br.readLine().trim().split(" ");
    for(int i=0;i<n;i++)
        arr[i] = Integer.parseInt(s[i]);
    
    maketree(0, 0, n-1, arr, tree);

    int q = Integer.parseInt(br.readLine().trim());
    while(q>0){
        q--;
        s = br.readLine().trim().split(" ");
        int x = Integer.parseInt(s[0]);
        int y = Integer.parseInt(s[1]);
        x--;y--;
        int ans = query(0,0,n-1,x,y,tree);
        System.out.println(ans);
        
    }
 

}

}

I am unable to understand why i am getting WA.:confused:

Read the question again :slight_smile:
It says to find maximum sum in range the x and y, not range maximum query.

You have to use kadane algorithm to solve the problem, IG. :blush:

I think you have wrongly understood the problem.
The problem is not to find the maximum in range l to r.
But it’s like a maximum sum subarray in the range l to r

1 Like

My bad.Thank you so much. I read it again after wasting 6 hours :expressionless:
I think kadane will TLE.
Its a segment tree problem.I guess.

Thanks for help. But I think it is
maximum sum subsequence in the range l to r.

Again you are wrong.
It’s max sum subarray within given range.
Read the question again
i is going on like i, i+1, i+2 , . . . . .upto j

Yup you are right. Thanks for help.:blush:

I think he is talking about building Kadane’s DP array for each node in the Segment Tree. That is, instead of storing a single number you store an array in each of the Segment Tree node. This would take $O(N * log(N))$ time for building the Segment Tree . If along with the Kadane’s DP array you also store the Max of DP array in each node then you can answer each query in $O(log(N))$.

I solved it using Segment tree.

There is a good explanation in this link , with the subtitle Finding subsegments with the maximal sum

1 Like

Time Complexity to build the segment tree will be O(N) and each query will be executed in O(logn) . For every node keep information about three things. 1) max_prefix_sum 2) max_suffix_sum 3) max_sum.