2
\$\begingroup\$

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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
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.LinkedList;
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);
}



}
 }
\$\endgroup\$
2
\$\begingroup\$
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?

Make your variable names clearer, and add comments what it does.

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.