# "Can you answer these queries I" challenge

I have tried to solve the following problem on SPOJ.com:

You are given a sequence

A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 )


A query is defined as follows:

Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }


Given M queries, your program must output the results of these queries.

When I run it, I get a time limit error, but I don't know why.

import java.awt.Point;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.sql.PreparedStatement;
import java.text.Collator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

class TestClass {

static int[] dist ;
static int[][][] vis;
static ArrayList<Integer>[] resu;
static char[][] graph;
static int max;
static int min;
static int[] dp;
static int zz;
static int zzz;
static nodes[] som;
static nodes temp;
static boolean fin;

static class nodes{

int sum ;
int presum;
int suffsum;
int max;

public nodes(){

}
public nodes(int sum , int presum , int suffsum , int max){

this.sum = sum;
this.presum = presum;
this.suffsum = suffsum;
this.max = max;
}
}

public static nodes merge(nodes a , nodes b){

nodes result = new nodes();

result.sum =  a.sum + b.sum;
result.presum = Math.max(a.presum, a.sum + b.presum);
result.suffsum = Math.max(b.suffsum, b.sum+a.suffsum);
result.max  = Math.max(Math.max(a.sum, b.sum), a.suffsum+b.presum);

return result;

}

public static void maketree(int current ,int a , int b ,int[] arr){
//  System.out.println(a+" "+b+" "+current);
if(a>b) return;

if(a==b)
{
int x = arr[a];
nodes newnode = new nodes(x,x,x,x);
som[current] = newnode;
return;
}

maketree(2*current, a, (a+b)/2, arr);
maketree(2*current+1, (a+b)/2+1, b, arr);

som[current] = merge(som[2*current], som[2*current+1]);

}

public static nodes query(int current , int a, int b, int i , int j){

if(a==i && b==j) return som[current];

int mid = (a+b)/2;

if(j<=mid) return query(2*current, a, (a+b)/2, i, j);
else if(i>mid) return query(2*current+1, (a+b)/2+1, b, i, j);
else{

return merge(query(2*current, a, (a+b)/2, i, j), query(2*current+1, (a+b)/2+1, b, i, j));
}
}

public static void main(String args[] ) throws IOException  {

Scanner in = new Scanner(new InputStreamReader(System.in));

int n = in.nextInt();
int[] a = new int[n+1];
som = new nodes[10000000];
for(int i=1;i<=n;i++) a[i]=in.nextInt();

temp = new nodes(Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE);

maketree(1, 1, n, a);

int Q = in.nextInt();

for(int i=0;i<Q;i++){

int l =in.nextInt();
int r =in.nextInt();
System.out.println(query(1, 1, n, l, r).max);
//System.out.println(som[2].max+ " "+ som[4].max +" "+ som[5].max);
}

}
}


static int[] dist ;
static int[][][] vis;
static ArrayList<Integer>[] resu;
static char[][] graph;
static int max;
static int min;
static int[] dp;
static int zz;
static int zzz;
static nodes[] som;
static nodes temp;
static boolean fin;


Your variable names are very hard to understand. What's dist? Distance? Then why is it an array? What's vis? Visuals? Why is it a 3D array?

Also, there is inconsistent spacing. You do stuff like:

static int[] dist ;


and you also do:

static int[][][] vis;


Be consistent. The conventions are "no space before ;", so this:

static int[][][] vis;


is correct. Also:

static class nodes{


Standard conventions for class names are PascalCase, not camelCase or alllowercase.

Also, I think all your variables need some breathing space:

if(j<=mid) return query(2*current, a, (a+b)/2, i, j);


should be:

if(j <= mid) return query(2 * current, a, (a + b) / 2, i, j);


Also, your formatting seems messed up. You have extra spaces everywhere, so try removing them.