I am trying to solve the above mention problem. Here is the link to the problem: http://www.spoj.com/problems/GSS1/
Here is my code:
import java.util.*;
import java.io.*;
public class Solution{
static void segTree(int[] arr, int[] seg, int low, int high, int pos){
if(high == low){
seg[pos] = arr[low];
return;
}
int mid = (high + low) / 2;
segTree(arr, seg, low, mid, 2 * pos + 1);
segTree(arr, seg, mid + 1, high, 2 * pos + 2);
int sum = seg[2 * pos + 1]+seg[2 * pos + 2];
int temp = Math.max(seg[2 * pos + 1], seg[2 * pos + 2]);
seg[pos] = Math.max(temp, sum);
}
static int sumMax(int[] seg, int qlow, int qhigh, int low, int high, int pos){
if(qlow <= low && qhigh >= high)
return seg[pos];
if(qlow >= high || qhigh <= low)
return Integer.MIN_VALUE;
int mid = (low+high) / 2;
return Math.max(sumMax(seg, qlow, qhigh, low, mid, 2*pos+1), sumMax(seg, qlow, qhigh, mid+1, high, 2*pos+2));
}
static class FastScanner implements Closeable {
BufferedReader in;
StringTokenizer st;
FastScanner() throws IOException {
in = new BufferedReader(new InputStreamReader(System.in));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
st = new StringTokenizer(line);
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
public void close() throws IOException {
in.close();
st = null;
}
}
public static void main(String[] args) throws IOException {
try(FastScanner sc = new FastScanner();
PrintWriter out = new PrintWriter(System.out)){
int n = sc.nextInt();
int[] arr = new int[n];
int size = (int)Math.ceil(Math.log(arr.length)/Math.log(2)) + 1;
int seg_size = (int)Math.pow(2, size) - 1;
int[] seg = new int[seg_size];
Arrays.fill(seg, Integer.MIN_VALUE);
for(int i = 0; i < n; i++)
arr[i] = sc.nextInt();
segTree(arr, seg, 0, arr.length - 1, 0);
int m = sc.nextInt();
while(m-- > 0){
int i = sc.nextInt();
int j = sc.nextInt();
i--;j--;
out.println(sumMax(seg, i, j, 0, arr.length - 1, 0));
}
}
}
}
I am not able to understand what I am doing wrong.
Thank you!