The first thing to notice is that there are only two specific cases where it's not possible to get a positive product. So I think an algorithm should first check if those specific cases are happening, then call a different subalgorithm for each of the three possible situations:
- it is possible to get a positive product, so we want to find the highest positive product;
- one of the arrays is full of zeroes, so all products are zero;
- it is impossible to get a positive product, because no array has both positive and negative numbers, and there is an odd number of arrays with only negative numbers, so we want to find the closest to zero negative product.
The second and third cases lead to trivial algorithms.
Let's consider the first case.
For every array, the only numbers that can be useful in the highest product are the highest positive number, and the lowest negative number. If an array only has positive numbers or only has negative numbers, then there is only one useful number in that array, which can be chosen immediately.
For all the remaining arrays, you have to choose whether to use the positive or the negative number. Ideally, you want to use the one with the highest absolute value; but if you do that for every array, then the result might be negative.
This leads to a linear algorithm:
- For all of the remaining arrays, initially select the number with the highest absolute value
- If the resulting product is positive, you're done.
- If the resulting product is negative, then a compromise has to be done in one of the arrays. For every array, compute the "cost" of this compromise (equal to the difference between the absolute values of the two interesting numbers in that array, multiplied by the product of all the other selected numbers).
- Finally, choose the array whose cost is the lowest, and change the chosen number in that array.
Here is an example execution of the algorithm on the list of arrays [[18,19,20,-23], [12,-10,9,8],[-10,-3],[5,3],[-10,-5]]
.
Here we notice that it is possible to find a positive solution, because at least one of the arrays contains both negative and positive numbers.
For the last three arrays we have no choice between positive and negative: so we can already choose -10, 5 and -10 as the three numbers for these three arrays. For the first array, we'll have to choose between 20 and -23; and for the second array we'll have to choose between 12 and -10.
So the final product will be: (20 or -23) * (12 and -10) * (-10) * 5 * (-10)
.
Ideally, we would prefer 23 to 20, and 12 to 10. That would result in:
(-23) * 12 * (-10) * 5 * (-10)
Unfortunately, this is negative. So the question is: do we replace -23 with 20, or 12 with -10?
The cost of replacing -23 with 20 would be (23-20) * 11 * (10*5*10) = 33 * (10*5*10)
.
The cost of replacing 12 with -10 would be (12-10) * 21 * (10*5*10) = 42 * (10*5*10)
.
Finally, we choose to replace -23 with 20, because that is the less costly compromise.
The final product is 20 * 12 * (-10) * 5 * (-10)
.