1800 - Maximum Subset of Array

maxsubsetarray.cpp

#include <iostream>
#define MODN 1000000009;
using namespace std;

long long modPot(long long n){
	long long i = n, x = 2, r = 1;
	while (i > 0){
		if (i % 2 != 0)
			r = r * x % MODN;
		x = x * x % MODN;
		i /= 2;
	}
	return r;
}

int main(){
	cin.sync_with_stdio(false);
	int T, N, in, z, i;
	long long c, mx;
	int sb[50001];
	cin >> T;
	while(T--){
		z = i = c = 0;
		cin >> N;
		cin >> sb[i];
		mx = sb[i];
		if(!mx) z++;
		for(i = 1; i < N; i++){
			cin >> sb[i];
			if(sb[i] == 0){ z++; if(mx < 0) mx = 0;}
			else if(sb[i] > 0 && mx > 0) mx += sb[i];
			else if(sb[i] > 0 && mx <= 0) mx = sb[i];
			else mx = mx < sb[i] ? sb[i] : mx;
		}
		if(mx < 0){ 
			for(i = 0; i < N; i++) 
				if(sb[i] == mx) c++;
		}
		else{
			if(!z) c++;
			else c = modPot(z);
			if(!mx) c-=1;
		}
		cout << mx << " " << c << endl;
	}
	return 0;
}