# SPOJ GSS1 challenge (maximum subarray sum) using Java

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 am using a segment tree and getting a TLE after test case 10:

import java.util.*;
import java.io.*;

public class Solution{

static void segTree(int[] arr, int[] seg, int low, int high, int pos){

if(high == low){
seg[pos] = arr[low];
return;
}

int mid = (high + low) / 2;

segTree(arr, seg, low, mid, 2 * pos + 1);
segTree(arr, seg, mid + 1, high, 2 * pos + 2);
int sum = seg[2 * pos + 1]+seg[2 * pos + 2];
int temp = Math.max(seg[2 * pos + 1], seg[2 * pos + 2]);
seg[pos] = Math.max(temp, sum);
}

static int sumMax(int[] seg, int qlow, int qhigh, int low, int high, int pos){

if(qlow <= low && qhigh >= high)
return seg[pos];

if(qlow >= high || qhigh <= low)
return Integer.MIN_VALUE;

int mid = (low+high) / 2;

return Math.max(sumMax(seg, qlow, qhigh, low, mid, 2*pos+1), sumMax(seg, qlow, qhigh, mid+1, high, 2*pos+2));
}

static class FastScanner implements Closeable {
StringTokenizer st;
FastScanner() throws IOException {
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens()) {
if (line == null) {
return null;
}
st = new StringTokenizer(line);
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
public void close() throws IOException {
in.close();
st = null;
}
}

public static void main(String[] args) throws IOException {
try(FastScanner sc = new FastScanner();
PrintWriter out = new PrintWriter(System.out)){

int n = sc.nextInt();
int[] arr = new int[n];

int size = (int)Math.ceil(Math.log(arr.length)/Math.log(2)) + 1;

int seg_size = (int)Math.pow(2, size) - 1;
int[] seg = new int[seg_size];
Arrays.fill(seg, Integer.MIN_VALUE);

for(int i = 0; i < n; i++)
arr[i] = sc.nextInt();

segTree(arr, seg, 0, arr.length - 1, 0);

int m = sc.nextInt();
while(m-- > 0){
int i = sc.nextInt();
int j = sc.nextInt();
i--;j--;
out.println(sumMax(seg, i, j, 0, arr.length - 1, 0));
}

}
}
}

• There are plenty of people complaining about tle with java because of input/output read/write times – juvian Jul 18 '17 at 14:13
• Is my logic correct or it can be further optimised? – lord_ozb Jul 18 '17 at 14:41
• Consider doing an exhaustive test of your algo with N=4, |A[i]|< 3 versus an obviously correct brute-force solution. – Deduplicator Jul 18 '17 at 14:50
• It seems like this could be done with nested loops - why the recursion? – Tamoghna Chowdhury Jul 19 '17 at 6:58
• Outer loop indexer j from x to y, inner loop indexer i from x to j - global maximum tracking variable, outer loop sum tracking variable. – Tamoghna Chowdhury Jul 19 '17 at 7:06