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
akashbhalotia:
2019-05-18 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:
2019-04-30 13:44:34
AC in Second GO :'( |
|
computer_argha:
2018-10-24 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 |
|
shizukaa:
2018-08-05 06:25:33
My first ac in one go! |
|
kishore_p:
2018-07-19 17:23:47
AC in one Go :)
|
|
rkocharyan:
2018-03-20 09:59:57
@alexandro5432 Yes, Abelyan Last edit: 2018-03-20 10:00:15 |
|
alexandro5432:
2018-03-15 15:08:15
shakil0302 y1 is a constant name in library cmath. Thats why you are getting compile errors. |
|
shakil0302:
2017-09-23 08:25:25
Anybody tried 'long long y1' as variable? Costs me 2 compiler error!! |
|
beginner_1998:
2017-09-14 00:02:31
weak test cases
|
|
shahidul_brur:
2016-11-13 12:21:52
why for the first query (i.e. 1 1 2 3) ans is 2 ?
|
Added by: | Frank Rafael Arteaga |
Date: | 2008-08-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | K.-Y. Chen and K.-M. Chao, On the Range Maximum-Sum Segment Query Problem, 2007. |