GSS1  Can you answer these queries I
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 xi and yi.
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
hide comments
heartless_2811:
20200323 14:31:49
help me debugging this code !! I think it's failing on test case 9 https://ideone.com/5Efoaw 

shanto09:
20200323 08:43:26
A problem worth solving! 

vritta:
20200322 11:14:34
For the newbies you can see explanation on my blog(read the comments for explanation), copy the code on your IDE & remove unnecessary comments it will become short "https://spojsolutionsgss1.blogspot.com/2020/03/pre.html" 

herrdirektor:
20200317 17:00:18
solved after many attempts. Total satisfaction after solving this one


omega1100100:
20200315 05:27:23
I solved it with Java & Segment Tree after 7 attempts. Last edit: 20200315 05:27:50 

sharjeel_spoj:
20200310 20:05:23
1 based indexing has been used for query range inputs. 

priyansh19077:
20200302 18:01:16
Getting a wrong answer on test case 9. Does anybody know where I could be going wrong 

priyansh19077:
20200302 17:58:55
We need to find the maximum value in the range given as a query right. Does that plus sign between the elements of the array signify anything or it's just there without any reason? 

jorge_iba:
20200301 21:07:06
For WA in test case 9 try to check if you Merge function it's okay at the moment of answering the queries, it's not the same Merge( Ans, Current) and Merge(Current, Ans). 

mrmajumder:
20200202 18:09:55
Learned segmented tree to solve this.

Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 