GSS5  Can you answer these queries V
You are given a sequence A[1], A[2], ..., A[N] . ( A[i] <= 10000 , 1 <= N <= 10000 ). A query is defined as follows: Query(x1,y1,x2,y2) = Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 <= j <= y2 and x1 <= x2 , y1 <= y2 }. Given M queries (1 <= M <= 10000), your program must output the results of these queries.
Input
The first line of the input consist of the number of tests cases <= 5. Each case consist of the integer N and the sequence A. Then the integer M. M lines follow, contains 4 numbers x1, y1, x2 y2.
Output
Your program should output the results of the M queries for each test case, one query per line.
Example
Input: 2 6 3 2 1 4 5 2 2 1 1 2 3 1 3 2 5 1 1 1 1 1 1 1 Output: 2 3 1
hide comments
canhnam357:
20211223 06:51:13
subarray with at least one element so sum maybe negative :") 

Abhishek Jaisingh:
20210510 15:12:49
AC after multiple attempts. Great brain exercise nevertheless. ;)


varunsainii:
20200520 17:57:10
AC in one go. But great brain exercise. 

zakir068:
20200225 09:44:41
Copied the Gss1 code + some implementation


hvh2911:
20191008 11:24:13
One HIT AC :V :V 

scorpy1:
20190913 04:52:55
AC in 1 GO! 

akashbhalotia:
20190518 18:58:32
The starting point of the maxSumSubarray should be [x1,y1] and the end point should be [x2,y2]. This is what the question is asks. 

saeedsab:
20190430 13:44:34
AC in Second GO :'( 

computer_argha:
20181024 13:54:40
Though the problem statement states that the size of the array is less than or equal 10000 but test cases have array size more than that so take a larger sized array to solve the problem 

tanardi gunawan:
20181003 13:06:30
Last edit: 20181003 13:11:28 
Added by:  Frank Rafael Arteaga 
Date:  20080806 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  K.Y. Chen and K.M. Chao, On the Range MaximumSum Segment Query Problem, 2007. 