VTOYS - Editorial

editorial
,
1

PROBLEM LINK:

Contest

Author: Kanhaiya Mohan
Tester: Syed Ali Atif
Editorialist: Hardik Chhabra, Naman Dhingra

DIFFICULTY:

Easy

PREREQUISITES:

Basic Math

Quick Explanation:

The problem is analysed in 3 parts , dealing with positive, negative no’s and zero. We will be storing all the negative integers separately, product of the positive numbers and a bool variable to know whether we encountered a zero.We will be forming the max product using the above information .

Explanation:

First observation is that if an element is positive, it cannot decrease the product, but only increase it or keep it as it is. Thus, we will multiply all the positive numbers for the answer.
Then, we consider the negative elements. If we take an odd number of negative elements, the final product will be negative which is not optimal. Instead, taking an even number of negative elements will only increase the product.
Checking the number of negative elements in the array, if it is even then all of them can be taken in the product else we will leave out the element with the smallest magnitude.
Now the special case, if there is only one negative element and zeros, the maximum product will be 0. For example { 0, -10, 0 }. The maximum product possible is 0.

SOLUTION:

Setter’s Solution 
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n;

void solve()
{
	cin>>n;
	int a[n];
	vector<int> neg;
	bool zero = false;
	int pos = -1;
	rep(n)
	{
		cin>>a[i];
		if(a[i]<0)
		{
			neg.push_back(a[i]);
		}
		else if(a[i]>0)
		{
			if(pos==-1)
			{
				pos = a[i];
			}
			else
			{
				pos *= a[i];
			}
		}
		else
		{
			zero = true;
		}
	}

	if(neg.size()==0)
	{
		if(pos!=-1)
			cout<<pos;
		else
		{
			cout<<0;
		}
		return;
	}

	if(neg.size()==1)
	{
		if(pos!=-1)
			cout<<pos;
		else if(zero)
			cout<<0;
		else
			cout<<neg[0];
		return;
	}
	sort(neg.begin(),neg.end());
	int negproduct = 1;
	for(int i = 0;i<neg.size();i+=2)
	{
		if((i+1)!=neg.size())
		{
			negproduct *= (neg[i]*neg[i+1]);
		}
	}

	int ans = negproduct;
	if(pos!=-1)
	{
		ans *= pos;
	}

	cout<<ans;
}

int32_t main()
{

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	sync;
	int t = 1;
	cin>>t;
	while(t--){
		solve();
		cout<<"\n";
	}
	return 0;
}