[Java] Maximum product of three elements in array

Given an array of integers with possible duplicates, negatives and zeros, find the largest product that can be made using three elements in the array.

We notice that if the array was sorted, we would have the smallest (possibly negative) elements at the beginning and the largest (also possibly negative) at the end.

Given an ordered sequence of elements, we can find the largest product in two ways:

• pick the 3 largest elements and multiply them together: if they are all positive, that is the maximum achievable. If one is 0, it's also the maximum as all other elements would either be 0 or negative, giving a smaller value than 0. If all are negative, the result would be the biggest negative number that can be made by multiplying those elements.
• pick the 2 smallest and the largest and multiply them together: this is to consider the case where the smallest elements are both negative and their multiplication would return a positive, multiplying them with the biggest will yield the largest product for those three elements

By choosing the biggest of those two, we have our answer. This could be done in O(N log N) time and space for sorting.

But we then notice that all we need are 5 elements: 3 largest ones and 2 smallest ones, we can simply create 5 variables and scan the array in one pass in O(N) time and constant space to track those elements to achieve the same result.

Careful: the if conditions to decide which elements to track must be chained together otherwise you might propagate the largest/smallest element everywhere.

You can check my implementation of maxThreeProduct on my Gist along with some tests in MaxThreeProductJTests.