Given an array a, your goal is to find the minimum product possible with the subset of elements of the array and store it to the variable res.

Examples

a = [1,8,3,-6,-2,-1]

res = 1*8*3*(-6)*(-2)*(-1) = -288

a = [-2,-1,0,9]

res = -2*9=-18

a = [0, 999]

res = 0

a = [-3, 5]

res = -3 * 5= -15

Greedy Approach

The goal is to reach the maximum absolute value of the product, i. e. use as many elements as possible until the product is negative. Thus, you have to use an odd number of negative elements of the array. By the way, pay attention to the 0 elements: it makes sense to use it in some cases, although it makes the product equal to 0.

Let’s explore different cases of elements in the array:

• There is at least one negative integer. If you multiply the odd amount of them, you’ll get some negative value, right? So, the goal is to take as many huge negative numbers as possible, but only an odd amount. Pick the maximum odd amount of them, i. e.: if there are 2*n-1 integers, pick them all, else if 2*n – pick them all, and remove one integer with the smallest absolute value. After that, increase the abs value of your res by multiplying all positive integers in the array (not 0!)

• There are only positive integers: pick the single smallest number, and there is an answer. If you multiply more, you'll increase the result.

• There are only positive integers and 0: think to yourself, what’s your decision?

Following this, you can build an algorithm using these cases.