Max product of the three numbers for a given array of size N

Question

I need to write a program to find the Max product of three numbers for a given array of size N. Is there any effective algorithm for this? I just need to know the algorithm steps. Non of algorithms that i thought works for all the test cases. Thanks! FYI Array may contains +ve, -ve, or zero elements)

Answer 1

Find the three largest numbers in the array (n1, n2, n3) and the two smallest numbers (m1, m2).

The answer is either n1 x n2 x n3 or n1 x m1 x m2

Answer 2

The method get the max product of 3 consists in basically find the biggest 3 numbers from the array and the smallest 2 numbers from the array in just 1 iteration over the array. There are of course a large variety of solutions but this is the optimal 1 because the time to solve the problem is O(n), the other solutions time is O(n lg n)

Here is the java code: by the way there is a guarantee that the input array is non empty and contains minimum 3 elements so there is no need to extra checks for empty and so on.

  int solution(int[] a) {

/* the minimums initialized with max int to avoid cases with extreme max in array and false minims 0 minimums returned */

int min1 = Integer.MAX_VALUE;

int min2 = Integer.MAX_VALUE;

/* the same logic for maximum initializations but of course inverted to avoid extreme minimum values in array and false 0 maximums */

    int max1 = Integer.MIN_VALUE;
    int max2 = Integer.MIN_VALUE;
    int max3 = Integer.MIN_VALUE;

//the iteration over the array

    for (int i = 0; i < a.length; i++) {

//test if max1 is smaller than current array value

        if (a[i] > max1) {

/* store the max1 current value in a temp var to test it later against the second maximum here as you can see is a chain of changes if is changed the biggest max we must change the other 2 */

            int tempMax1 = max1;

//assign the current array value as maximum

            max1=a[i];

//test tempMax1 former max1 value against max2

            if(tempMax1>max2){

/* store max2 value in tempMax2 value to test it against max3 and assign it to max 3 if it's bigger */

                int tempMax2 = max2;
                max2 =tempMax1;
                if(tempMax2>max3){
                    max3 = tempMax2;
                }

/* test to see if tempMax1 is bigger if isn't bigger than max3, this is happening when max1 gets a new value and the old value of max1 is equal with max2 but bigger than max3 */

            }else{
                if(tempMax1>max3){
                    max3 = tempMax1;
                }
            }

/* in case if current a[i] isn't bigger than max1 we test it to see maybe is bigger than second max. Then the same logic from above is applied here to max3 */

        }else if(a[i]>max2){
            int tempMax2 = max2;
            max2 = a[i];
            if(tempMax2>max3){
                max3 =tempMax2;
            }

/* finally if current array value isn't bigger than max1 and max2 maybe is greater than max3 */

        }else if(a[i]>max3){
            max3 = a[i];
        }

/* The logic from above with maximums is is applied here with minimums but of course inverted to discover the 2 minimums from current array. */

        if (a[i] < min1) {
            int tempMin1 = min1;
            min1 = a[i];
            if (tempMin1 < min2) {
                min2 = tempMin1;
            }
        } else if (a[i] < min2) {
            min2 = a[i];
        }
    }

/* after we discovered the 3 greatest maximums and the 2 smallest minimums from the array we do the 2 products of 3 from the greatest maximum and the 2 minimums . This is necessary because mathematically the product of 2 negative values is a positive value, and because of this the product of min1 * min2 * max1 can be greater than max1 * max2 * max3 and the product built from the the 3 maximums. */

    int prod1 = min1 * min2 * max1;
    int prod2 = max1 * max2 * max3;

//here we just return the biggest product

    return prod1 > prod2 ? prod1 : prod2;

}