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.
-1 -1 -1
2 0 -2 2
1 <= T <= 35
1 <= n <= 100000
-1000 <= Ai <= 1000
use kadane's algo along with count array
Finally AC after 4 WA and 2 TLE.
accepted using scanf and printf
map -> TLE
Use long long for "the number of sequences which obtains this maximum sum".
@reddragon the first element only, the first and the second, the last element only, the whole array
Can be done in O(n) time and O(1) space without any casing :)
Nice Problem!!learned many new thngs
can somebody explain second test case . I think output should be : 2 3