| Submit | All submissions | Best solutions | Back to list |
MAXSUMSQ - Maximum Sum Sequences |
Given an array A having n elements, let X be the maximum sum of any contiguous sequence in the array. How many contiguous sequences in A sum up to X?
Input
The first line contains T the number of test cases. There follow 2T lines, 2 for each test case. The first line contains the n, the number of elements in the array. The second line contains n space separated integers Ai.
Output
Output T lines, one for each test case. On each line, output two space separated integers; the maximum sequence sum, and the number of sequences which obtain this maximum sum.
Example
Input: 2
3
-1 -1 -1
4
2 0 -2 2 Output: -1 3
2 4
Constraints
1 ≤ T ≤ 35
1 ≤ n ≤ 100000
-1000 ≤ Ai ≤ 1000
| Added by: | Varun Jalan |
| Date: | 2010-01-24 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
| Resource: | own problem used for Codechef Snackdown Onsite |
hide comments
|
||||||
|
2023-03-12 05:08:32
AC with map easily Last edit: 2023-03-12 05:08:51 |
||||||
|
2020-06-02 14:52:14
did it with BIT how to do it in O(N) though |
||||||
|
2019-04-14 10:44:41
Some points: 1) use scanf and printf, I got TLE with cin, cout even with fastio. 2)if you are using map, use unordered_map instead. |
||||||
|
2018-11-02 07:55:21
Can anyone have a look at my code for this problem and tell what is wrong?? <snip> Last edit: 2022-06-28 22:07:39 |
||||||
|
2018-03-10 08:31:39
use kadane's algo along with count array |
||||||
|
2017-04-06 20:11:26
Finally AC after 4 WA and 2 TLE. |
||||||
|
2017-02-05 09:01:49 pranay
accepted using scanf and printf got tle using cin and cout |
||||||
|
2017-02-03 23:09:05 Dushyant Singh
map -> TLE unordered_map -> AC |
||||||
|
2016-11-02 02:27:25
Use long long for "the number of sequences which obtains this maximum sum". The constraints of the problem allow this 'max_count' field to be > (n/2)^2, where n is 10^5 Thanks @Ankit Sultana! |
||||||
|
2016-08-20 06:05:41
@reddragon the first element only, the first and the second, the last element only, the whole array |
||||||
RSS