# GSS1 SPOJ problem Time Limit Exceeding

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));
}
}
}


## 1 Answer

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.