1
\$\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 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 {
BufferedReader in;
StringTokenizer st;
FastScanner() throws IOException {
    in = new BufferedReader(new InputStreamReader(System.in));
}
String next() throws IOException {
    while (st == null || !st.hasMoreTokens()) {
        String line = in.readLine();
        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));                    
            }

        }
    }
 }
\$\endgroup\$
  • \$\begingroup\$ There are plenty of people complaining about tle with java because of input/output read/write times \$\endgroup\$ – juvian Jul 18 '17 at 14:13
  • \$\begingroup\$ Is my logic correct or it can be further optimised? \$\endgroup\$ – lord_ozb Jul 18 '17 at 14:41
  • \$\begingroup\$ Consider doing an exhaustive test of your algo with N=4, |A[i]|< 3 versus an obviously correct brute-force solution. \$\endgroup\$ – Deduplicator Jul 18 '17 at 14:50
  • \$\begingroup\$ It seems like this could be done with nested loops - why the recursion? \$\endgroup\$ – Tamoghna Chowdhury Jul 19 '17 at 6:58
  • \$\begingroup\$ 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. \$\endgroup\$ – Tamoghna Chowdhury Jul 19 '17 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.