2
\$\begingroup\$

The problem is presented here 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));
    }
}
}
\$\endgroup\$
3
\$\begingroup\$

I can't suggest any optimization. The complexity of the algorithm is N*logN in both setup and execution time. The task however has a (sub)linear solution.

Since this is a competitive problem, I am sure it is unethical to show the code; I am not even sure it is ethical to describe an algorithm. Besides the fact that a linear solution exists, I can afford one more hint:

View the data set as a sequence of runs of positive and negative values. Notice that each run either completely belongs to an optimal range, or is completely excluded from it. Given a current best, and a sequence CNP (C being a current candidate, N a next run of negatives, followed by the run P of positives) figure out the conditions when restarting at P is better than accepting CNP as next candidate.

Please forgive me, I am intentionally vague. Yet again, the mere fact that a linear algorithm exists is a very strong hint.

\$\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.