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).

Solution 1

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

Solution 2

For count=3, your solution will have 1 of 3 forms:

1. The 3 largest positive values (assuming there ARE 3 positive values)

2. The largest positive value and the 2 smallest negative values (assuming there IS a positive value)

3. The 3 least negative values

Each of which can be solved a lot easier than using DP.

Solution 3

It is always max of(smallest two negative digits and biggest positive or last three big positive numbers)

public static void main(String args[]){

    int array[] = {-5,-1,4,2,1,9};
    Arrays.sort(array);

    int length = array.length;
    System.out.println(max(array[0]*array[1]*array[length-1], 
                           array[length-1]*array[length-2]*array[length-3]));   
}

Solution 4

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.

Solution 5

Sort The Array

Then max will be either the product of last 3 or first 2(if negative) and the last.

 Arrays.sort(arr);
 int max1 = (arr[n - 1] * arr[n - 2] * arr[n - 3]);
 int max2 = (arr[0] * arr[1] * arr[n - 1]);
 System.out.println(max1 > max2 ? max1 : max2);

View more solutions

Comments

[TypeIA]

It could also be 2 positive values and 1 negative value; consider the trivial case { -1, 1, 2 }.

[Kendall Frey]

Assuming you are assuming absolute values, judging by #3, there will be a fourth case, which is the 2 largest numbers and the lowest negative number, in which case everything collapses to one case, which is the 3 numbers farthest from 0.

[Scott Hunter]

@Kendall Frey: I wasn't assuming absolute values; for #3, I meant the negatives w/ the SMALLEST absolute value (if all values are negative, your result will be negative, so you're shooting for the negative closest to 0).

[Kendall Frey]

@ScottHunter Ah, I see.

[user3011937]

So, we have to iterate over the array for all the 3 cases, and then find out the 3 values for all of them? Any easy way?

[SubSevn]

You might also be able to do this without sorting by iterating over the array once and simply storing the three largest/smallest values.

[SubSevn]

Case 3 will only occur in the event that you have an array made up of entirely negative values - at which point you're really just doing a generalization of Case 1: the three largest values.

[user3011937]

Ok, all the cases done. But it just fails for {-2, 3, 4}, as specified by @David. Will add a case for this one, and I think it will be done.

[Deepend]

It is useful if you can add some additional information about your methodology

[greybeard]

How does this differ from Scott Hunter's answer, with the case for 2 positive values and 1 negative value amended?

[Doron Segal]

what about negative values

[Doron Segal]

@maandoo got it thanks, btw that's my solution in Javascript github.com/doron2402/algorithm-interviews/blob/master/…

[Joshi]

what if all the elements are negative? I think this will not work. Should we also check first 3 elements' product as well?

[ciamej]

If there are less than 3 positive values, we should check if the array contains zero. Multiplying be zero might yield the highest result!

[Claire Furney]

You also need to consider the case where all items in the list are negative.

[GoodPerson]

It's not correct. If you make abs on [-9,8,2,4] and then sort, it results in [2,4,8,9] and product will be 9*8*4 = 288, but expected is 8*4*2 = 64

[greybeard]

(I appreciate your attempt to correct betwen, but - it was contraproductive.)

[greybeard]

Why follow open coded max determination with .sort()?