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
pratyushgadge1:
20231102 20:48:21
WA on case 9???? 

vishalrawat_1:
20230828 09:31:14
need a sherlock brain for the testcase where my code get failed


vikas_102:
20230612 15:24:39
i learnt a lot form this question.this question was equal to 5 seg t questions. 

iskhakkutbilim:
20230302 15:25:40
is it can be solved by segment tree(maximum subarray sum) 

xarma:
20230126 08:12:16
You should avoid printing answer for empty subarray (i.e 0) , They are asking for a subbarray with atleast one element Last edit: 20230126 08:12:35 

yszokk:
20221111 14:01:50
OMG.Quite Difficult:( 

rotcar07:
20220922 09:25:59
Why wrong answer on test #9? Did I missed something? 

ma_niu_bi:
20220830 14:06:37
Why? 

ma_niu_bi:
20220830 13:38:07
wrong answer on test #9? help! 

Phi:
20220815 14:01:47
I'm not sure I understand the query definition? Are we looking for a sum of a[i] up to a[j]? If yes, why do we need max{} then (it would be a max from a single value)? Or are we interested in a max over a[i] up to a[j]? If yes, why are there pluses between a[i]s? Last edit: 20220815 14:01:59 
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 