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
kshubham02:
2018-12-15 18:10:17
Problem statement is ambiguous, so here is some clarification : you need to find the maximum possible sum using a subset(not necessarily contiguous, non-empty) of the array. As many subsets can give the same maximum sum, also output the number of distinct such subsets.
|
|
sas1905:
2017-07-06 06:59:12
1000,000,009 NOT 1000,000,007!! 1 WA :( |
|
coolio_1:
2017-06-24 14:41:35
One Word!!! Modular exponentiation!! ( okay 2 words :-D)
|
|
geoffreymace7:
2017-05-31 17:40:57
Don't apply modulo operation on the sum of maximum subset. |
|
swatantragupta:
2016-12-25 11:26:53
language is confusing..comments helped:) |
|
Wumbolo:
2016-07-20 09:58:56
I don't like this problem, also the comments spoiled it. I didn't understand the problem at all so I looked in the comments. |
|
Dushyant Singh:
2016-04-21 22:30:03
"output the value of the maximum subset and the count of the subsets modulo 1000,000,009"
|
|
ROHIT Kumar:
2015-08-12 19:00:47
used modular expo....nice question...2 hr of brain sucking finally got ac |
|
rk:
2015-06-29 11:52:22
what m i going to state now is really funny despite of taking mod 10^9+9 i took mod with 10^9+7 which was present in my template before hand ,lol be aware of this :) and Nice question by the way
|
|
:.Mohib.::
2015-06-05 05:58:55
Nice que... I like it... :) |
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 |