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
theshumo:
2024-02-17 07:01:25
1
|
|
abhi_8:
2023-08-12 08:50:31
You can solve it, all the best! |
|
alphazero56:
2022-08-18 12:35:34
Good extension of GSS1 |
|
mindeveloped:
2022-08-08 14:39:02
This problem is Dless |
|
canhnam357:
2021-12-23 06:51:13
subarray with at least one element so sum maybe negative :") |
|
Abhishek Jaisingh:
2021-05-10 15:12:49
AC after multiple attempts. Great brain exercise nevertheless. ;)
|
|
varunsainii:
2020-05-20 17:57:10
AC in one go. But great brain exercise. |
|
zakir068:
2020-02-25 09:44:41
Copied the Gss1 code + some implementation
|
|
hvh2911:
2019-10-08 11:24:13
One HIT AC :V :V |
|
scorpy1:
2019-09-13 04:52:55
AC in 1 GO! |
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. |