Algorithm
problem link- https://www.spoj.com/problems/MAXSUB/
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
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
modulo = 1000000009
def power(a, b):
if b == 0:
return 1
if b % 2 == 1:
return power(a, b - 1) * a % modulo
half = power(a, b >> 1)
return half * half % modulo
T = int(input())
for c in range(T):
N = int(input())
assert N > 0
a = map(int, raw_input().split())
big = -1 << 30
sum = 0
zeroes = 0
count = 0
for i in a:
if i > big:
big = i
count = 1
elif i == big:
count += 1
if i > 0:
sum += i
if i == 0:
zeroes += 1
if big == 0:
print('0 %d' %(power(2, count) - 1))
elif big < 0:
print('%d %d' %(big, count % modulo))
else:
print('%d %d' %(sum, power(2, zeroes)))Input
5
1 -1 1 -1 1
6
-200 -100 -100 -400 -232 -450
Output
-100 2
Demonstration
SPOJ Solution-Maximum Subset of Array-Solution in C, C++, Java, Python