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 seperated integers Ai.
Output
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.
Example
Sample Input
2
3
1 1 1
4
2 0 2 2
Sample Output
1 3
2 4
Constraints
1 <= T <= 35
1 <= n <= 100000
1000 <= Ai <= 1000
hide comments
s_a_k_s_h_a_m:
20180310 08:31:39
use kadane's algo along with count array


kmkhan_014:
20171212 11:19:51
Awesome problem!!!


ydeepak1889:
20170406 20:11:26
Finally AC after 4 WA and 2 TLE. 

pranay:
20170205 09:01:49
accepted using scanf and printf


Dushyant Singh:
20170203 23:09:05
map > TLE


scottt:
20161102 02:27:25
Use long long for "the number of sequences which obtains this maximum sum".


amr_aly:
20160820 06:05:41
@reddragon the first element only, the first and the second, the last element only, the whole array 

hodobox:
20160809 18:32:38
Can be done in O(n) time and O(1) space without any casing :) 

rocode0001:
20151216 17:58:27
Nice Problem!!learned many new thngs


msa21974:
20151006 13:12:27
can somebody explain second test case . I think output should be : 2 3

Added by:  Varun Jalan 
Date:  20100124 
Time limit:  0.365s 
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 