The [problem is presented here](http://www.spoj.com/problems/GSS1/) as follows:

> 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.
> 
> **Input**
> 
> - The first line of the input file contains the integer \$N\$. 
> - In the second line, \$N\$ numbers follow. 
> - The third line contains the integer \$M\$. 
> - \$M\$ lines follow, where line \$i\$ contains 2 numbers \$x_i\$ and \$y_i\$. 
>
> **Output**
> 
> Your program should output the results of the \$M\$ queries, one query per
> line. 
>
> **Example**
> 
> *Input*: 
>
> 3 
>
> -1 2 3 
>
> 1 
> 1 2 
>
> *Output*: 
>
> 2

I'm solving the problem by using a segment tree - I am saving the sum, the max ,leftmost max, and the right most max at every node. I then search the graph to find the answer to a specific interval. How could I increase the speed of this code?


    import java.util.Scanner;
    //TLE
    class GSS1 {
    
    
    static class Node{
        int max;
        int MaxL;
        int MaxR;
        int sum;
        
        public Node(int max, int MaxL, int MaxR, int sum){
            this.max=max;
            this.MaxL=MaxL;
            this.MaxR=MaxR;
            this.sum=sum;
        }
        
        public Node(){
            
        }
    }
    
    static class SegmentTree{
        
        private Node[] tree;
        private int maxsize;
        private int height;
     
        private  final int STARTINDEX = 0; 
        private  final int ENDINDEX;
        private  final int ROOT = 0;
        Node s;
     
        public SegmentTree(int size){
            height = (int)(Math.ceil(Math.log(size) /  Math.log(2)));
            maxsize = 2 * (int) Math.pow(2, height) - 1;
            tree = new Node[maxsize];
            for(int i=0;i<tree.length;i++){
                tree[i]=new Node();
            }
            ENDINDEX = size - 1; 
            s=new Node();
            s.MaxL=Integer.MIN_VALUE;
            s.MaxR=Integer.MIN_VALUE;
            s.sum=Integer.MIN_VALUE;
            s.max=Integer.MIN_VALUE;
            
        }
        
        
        
        
        private int leftchild(int pos){
            return 2 * pos + 1;
        }
     
        private int rightchild(int pos){
            return 2 * pos + 2;
        }
     
        private int mid(int start, int end){
            return (start + (end - start) / 2); 
        }
        
        private Node constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current){
            if (startIndex == endIndex)
            {
                tree[current].max=tree[current].MaxL=tree[current].MaxR=tree[current].sum=elements[startIndex];    
                return tree[current];
            }
            int mid = mid(startIndex, endIndex);
            Node left=constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current));
            Node right=constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current));
            tree[current].max = Math.max(left.max, right.max);
            tree[current].MaxL = Math.max(left.MaxL , left.sum+right.MaxL);
            tree[current].MaxR = Math.max(right.MaxR , right.sum+left.MaxR);
            tree[current].sum = left.sum+right.sum;
            return tree[current];
        }
     
        public void constructSegmentTree(int[] elements){
            constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT);    
        }
     
        private Node getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current){
            
            if (queryStart <= startIndex && queryEnd >= endIndex ){
                return tree[current];
            }
            if (endIndex < queryStart || startIndex > queryEnd){
                return s;
            }
            int mid = mid(startIndex, endIndex);
            
            Node left=getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current));
            Node right=getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));
            
            Node current_Node=new Node();
            current_Node.max = Math.max(left.max, right.max);
            current_Node.MaxL = Math.max(left.MaxL , left.sum+right.MaxL);
            current_Node.MaxR = Math.max(right.MaxR , right.sum+left.MaxR);
            current_Node.sum = left.sum+right.sum;
            return current_Node;
            
            
        }
     
        public int getMaxSum(int queryStart, int queryEnd){
            if(queryStart < 0 || queryEnd > tree.length)
            {System.out.println("inside negative");
                return Integer.MIN_VALUE;
            }
            return getMax(getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT));
        }
        
        public int getMax(Node r){
            return Math.max(Math.max(r.max, r.MaxL),Math.max(r.MaxR, r.sum));
        }
        
        public int getFirst(){
            return tree[0].MaxL;
        }
        
    }

    
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        
        int numbers[]=new int [input.nextInt()];
        
        for(int i=0;i<numbers.length;i++){
            numbers[i]=input.nextInt();
        }
        
        SegmentTree tree=new SegmentTree(numbers.length);
        tree.constructSegmentTree(numbers);
        
        int cases=input.nextInt();
        
        int x;
        int y;
        int query;
        for(int i=0;i<cases;i++){
            x=input.nextInt()-1;
            y=input.nextInt()-1;
            
            System.out.println(tree.getMaxSum(x, y));
        }
    }
    }