The biggest product is two smallest negatives and one biggest positive.
The biggest product is negative itself(!), which can happen in at least these two distinct cases:
[n,p,p]: There are only 3 inputs, one of them negative. For any length 3 input we should just return the input anyway, implicitly or explicitly.
[n,n,n...]: There are 3 or more inputs, none of which are positive. In this case we should return the 3 negative numbers closest to 0 (3 biggest numbers, same as the all-positive happy case)
importmathdefget_product_of_3(array_of_ints):iflen(array_of_ints)<3:return0min_max=-math.infmin_max_i=0maxes=[min_max,min_max,min_max]max_neg=0max_neg_i=0negs=[0,0]forintinarray_of_ints:ifint>min_max:maxes[min_max_i]=intmin_max_i,min_max=min(enumerate(maxes),key=lambdax:x[1])ifint<max_neg:negs[max_neg_i]=intmax_neg_i,max_neg=max(enumerate(negs),key=lambdax:x[1])prod_maxes=maxes[0]*maxes[1]*maxes[2]prod_negs=negs[0]*negs[1]# This condition is only needed for `[n,p,p]`, to not return the invalid product of `0` when the product of maxes is negative.
ifprod_negs!=0:returnmax(prod_negs*max(maxes),prod_maxes)returnprod_maxes
If we instead explicitly return the product of 3 inputs, this condition is no longer needed:
Another possible optimization, for input such as [...-100,-99,-98,-97,1,-96,-95,-94...] is to stop expecting the "all negatives" case. This can easily be done by resetting all negative maxes to 0, so that incoming negatives are always smaller:
Thanks Mihail. This looks much more neat. Will test it out later.
But did you test the case if two negative numbers are passed?
For e.g [-5, -4, 1, 3, 2] -> should give 60.
Yes, I see the problem.
So far I see three cases:
[n,p,p]
: There are only 3 inputs, one of them negative. For any length 3 input we should just return the input anyway, implicitly or explicitly.[n,n,n...]
: There are 3 or more inputs, none of which are positive. In this case we should return the 3 negative numbers closest to 0 (3 biggest numbers, same as the all-positive happy case)I'll post a fix later, let's see how messy.
Okay, I think I got it:
If we instead explicitly return the product of 3 inputs, this condition is no longer needed:
Another possible optimization, for input such as
[...-100,-99,-98,-97,1,-96,-95,-94...]
is to stop expecting the "all negatives" case. This can easily be done by resetting all negative maxes to 0, so that incoming negatives are always smaller: