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