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.
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.
T <= 20
n <= 50,000
Each element in the array <= 1,000,000,000
For each test case output the value of the maximum subset and the count of the subsets modulo 1000,000,009
Input: 2 5 1 -1 1 -1 1 6 -200 -100 -100 -400 -232 -450 Output: 3 1 -100 2
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.
1000,000,009 NOT 1000,000,007!! 1 WA :(
One Word!!! Modular exponentiation!! ( okay 2 words :-D)
Last edit: 2017-06-08 12:15:38
Don't apply modulo operation on the sum of maximum subset.
language is confusing..comments helped:)
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.
"output the value of the maximum subset and the count of the subsets modulo 1000,000,009"
used modular expo....nice question...2 hr of brain sucking finally got ac
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