This is a simple question to find maximum between a given range in array.
Please help.
Question link - SPOJ.com - Problem 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);
}
}
}
