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 ?


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 seperated integers Ai.


Output T lines, one for each test case. On each line, output two space seperated integers; the maximum sequence sum, and the number of sequences which obtain this maximum sum.


Sample Input

-1 -1 -1
2 0 -2 2

Sample Output

-1 3
2 4


1 <= T <= 35
1 <= n <= 100000
-1000 <= Ai <= 1000

hide comments
black_shroud: 2020-06-02 14:52:14

did it with BIT
how to do it in O(N) though

anirudnits: 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.

gaurav1614: 2018-11-02 07:55:21

Can anyone have a look at my code for this problem and tell what is wrong??

Last edit: 2022-06-28 22:07:39
s_a_k_s_h_a_m: 2018-03-10 08:31:39

use kadane's algo along with count array

kmkhan_014: 2017-12-12 11:19:51

Last edit: 2018-09-08 08:37:59
ydeepak1889: 2017-04-06 20:11:26

Finally AC after 4 WA and 2 TLE.

pranay: 2017-02-05 09:01:49

accepted using scanf and printf
got tle using cin and cout

Dushyant Singh: 2017-02-03 23:09:05

map -> TLE
unordered_map -> AC

scottt: 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!

amr_aly: 2016-08-20 06:05:41

@reddragon the first element only, the first and the second, the last element only, the whole array

Added by:Varun Jalan
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem used for Codechef Snackdown Onsite