Find maximum product of 3 numbers in an array

Question

Given an array of integers, which can contain both +ve and -ve numbers. I've to maximize the product of any 3 elements of the array. The elements can be non-contiguous.

Some examples:

int[] arr = {-5, -7, 4, 2, 1, 9};  // Max Product of 3 numbers = -5 * -7 * 9
int[] arr2 = {4, 5, -19, 3};       // Max Product of 3 numbers = 4 * 5 * 3

I've tried solving it using Dynamic Programming, but I'm not getting the expected result. It is returning the result often involving the same number twice in the multiplication. So, for the array - {4, 2, 1, 9}, it is returning - 32, which is 4 * 4 * 2.

Here's my code:

public static int maxProduct(int[] arr, int count) {
    return maxProduct(arr, 0, arr.length - 1, count);
}

private static int maxProduct(int[] arr, int fromIndex, int toIndex, int count) {

    if (count == 1) {
        return maximum(arr, fromIndex, toIndex);
    } else if (toIndex - fromIndex + 1 < count) {
        return 1;
    } else {
        return MathUtil.max(maxProduct(arr, fromIndex, toIndex - 1, count - 1) * arr[toIndex - 1], 
                            maxProduct(arr, fromIndex, toIndex - 1, count));
    }
}

• MathUtil.max(int a, int b) is a method that gives maximum of a and b.
• The two values I pass to max method there are:
  • maxProduct, when we consider last element as a part of product.
  • maxProduct, when we don't consider it as a part of product.
• count contains the number of element we want to consider. Here 3.
• For count == 1, we have to find maximum of 1 element from array. That means, we have to use maximum array element.
• If toIndex - fromIndex + 1 < count, means, there are not enough elements in the array between those indices.

I've an intuition that, the first if condition is one of the reason of failure. Because, it is only considering maximum element from an array, while the maximum product may comprise of negative numbers too. But I don't know how to take care of that.

The reason I'm using Dynamic Programming is that I can then generalize this solution to work for any value of count. Of course, if someone have any better approach, even for count = 3, I welcome the suggestion (I would want to avoid sorting the array, as that will be another O(nlogn) at the least).

Answer 1

n=len(arr1)
    for i in range(0,n):
        arr1[i]=abs(arr1[i])
    arr1.sort()
    return arr1[n-1]*arr1[n-2]*arr1[n-3]

even though this solution is simple this basically involves sorting the array and then taking the product of last three numbers , before that is to be done ; all the values in the array should be positive .which is done by the first for loop.

Answer 2

Sort the given array in ascending order and you have to take the maximum of these cases to get the answer..

1. product of last 3 numbers in sorted array
2. Product of first two and last number in the sorted array

Answer 3

You can use inbuilt sort function of Javascript.Need to careful while finding max triplet product as in case of array with -ve numbers product will be combination first 2 and last and in case all +ve last 3 number product will be result.You can refer my jsfiddle. Also complexity of this algorithm is O(nlogn)

var arr=[-10, 3, 5, 6, -20];
function maxTripletProduct(data)
{
  var sortedarr=data.sort(function(a,b){
  return a-b;
})
console.log(sortedarr);

let length=sortedarr.length;
let product1 = sortedarr[length-3]*sortedarr[length-2]*sortedarr[length-1]
let product2=sortedarr[0]*sortedarr[1]*sortedarr[length-1];
if(product2>product1)
  console.log(product2);
else
  console.log(product1);
}
maxTripletProduct(arr);

Answer 4

Assuming that the a positive product is bigger than a negative product, I can think of the following way it can be done.

1. If there are less than two negative elements in the array, then it is simple, product of top 3(top == positive) elements.

2. If negative numbers are chosen, at least 2 of them have to be in the product, so that product is positive. Therefore whatever be the case, the top (positive) number will always be part of the product.

3. Multiply last two(negatives) and 2nd and 3rd highest(positives) and compare. Out of these two pairs whichever has higher value, will be part of the final product along with the top positive shortlisted in line above.