@linxingquan Just think about three cases:
all positive - product of last three
one negative - product of last three
two or more negative - either product of first two and last or product of last three
Aha, here is my thinking process. When A < 0 < A[-1], we know A[-1] is the maximum positive number and A is the minimum negative number in the array. Then, if A is negative, one possible answer can be A * A * A[-1].
And for the case when A is positive, A * A is negative and we wanna keep the three number product as small as possible by multiply another smallest number A. For example, the sorted A is [-1,1,2].
Wait a second, the example above actually within the answer A[-3]*A[-2]*A[-1]... Why are you so smart, Stefan.
@nachiketnaik Actually I take this back. This is very close, but it actually would not work for the case. [-2, -2, -2, -1] case. Your answer would return -8 (-2*-2*-2) since you are looking for the smallest among 3 negative numbers. But the correct answer should be -4 (-2*-2*-1)
With that said, I tried to find a O(n) solution as well, but I do not think there is a very 'clean' way. Best to just sort, which is probably what the problem intended us to do. @administrators should add that test-case in