MAXSUB - Maximum Subset of Array
Given an array find the sum of the maximum non-empty subset of the array and also give the count of the subset. A subset of an array is a list obtained by striking off some (possibly none) numbers.
A non-empty subset implies a subset with at least 1 element in it.
Input
First line contains an integer T which is the number of integers. Following this T-cases exist.
Each case starts with a line containing an integer n which is the number of elements in the array.
The next line contains n-integers which contain the value of this subset.
Constraints
T <= 20
n <= 50,000
Each element in the array <= 1,000,000,000
Output
For each test case output the value of the maximum subset and the count of the subsets modulo 1000,000,009
Example
Input: 2 5 1 -1 1 -1 1 6 -200 -100 -100 -400 -232 -450 Output: 3 1 -100 2
hide comments
Siya:
2014-11-17 14:36:36
Problem statement is not clear. |
|
bhim:
2014-10-08 22:15:02
@.:: Pratik ::. pls clearly explain about the modulo
|
|
P_Quantum:
2014-05-29 15:30:36
nice!! |
|
zicowa:
2014-02-02 13:08:22
i also did the same mistake |
|
CoNtRaDiCtIoN:
2013-12-14 16:08:23
take modulus of only the no of subsets not the max of the array ... costed me so many wa |
|
张翼德:
2012-12-16 02:39:08
easy test file :)
|
|
Zhiang:
2012-06-29 18:41:37
good one... :) |
|
Kartik A:
2012-06-15 11:58:22
Is ans for -1 -1 -1 0 0 is 0 3
|
|
akb:
2012-04-08 00:18:56
beautiful... |
|
SIDHANT SINHA:
2012-02-26 06:16:51
plz...clarify what is meant by "count of the subset" |
Added by: | .:: Pratik ::. |
Date: | 2011-03-07 |
Time limit: | 0.507s-2.450s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |