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

https://stackoverflow.com/users/2466168/maandoo 's answer is the best.

As, he said, answer is max(l,r) for

r. product of last 3 numbers in sorted array
l. product of first two and last number in the sorted array

Let me elaborate now.

I think this problem is confusion because each number can be positive, negative and zero. 3 state is annoying to mange by programming, you know!

---

Case 1) Given three numbers

• Use them all

---

Case 2) Given four numbers

• Positive number is show +, Negative number is show -.
• Numbers are sorted from left to right.

Case 2-1)

2-1) ---- => r (answer is negative)
2-2) ---+ => l (answer is positive)
2-3) --++ => l (answer is positive)
2-4) -+++ => r (answer is positive)
2-5) ++++ => r (answer is positive)

When a 0 is mixed in four numbers, it comes between - and +.

Case 2-2) Suppose smallest + was actually 0.

2-1) ---- => r (answer is negative)
2-2) ---0 => l (answer is 0)
2-3) --0+ => l (answer is positive)
2-4) -0++ => r (answer is 0)
2-5) 0+++ => r (answer is positive)

Case 2-3)

Suppose largest - was actually 0.

2-1) ---0 => r (answer is 0)
2-2) --0+ => l (answer is positive)
2-3) -0++ => l (answer is 0)
2-4) 0+++ => r (answer is positive)
2-5) ++++ => r (answer is positive)

Case 2-4)

If more than two 0 is mixed, products becomes always 0 because

-00+

---

Summary for Case 2)

answer is consistent among Case 2-1 ~ 2-4.

2-1) r (negative or 0)
2-2) l (0 or positive)
2-3) l (0 or positive)
2-4) r (0 or positive)
2-5) r (positive)

So, we do not need to worry about 0 actually.

---

Case 3) More than four numbers

• The same with Case 2

Answer 2

u have to consider 3 cases:
1. max 3 positive elements can be the first answer(say 10*20*70).
2. max positive elements multiplied by 2 most negative answers is another candidate(say20*-40*-60).
3.in case where all array elements are negative,3 elements with minimum negative magnitude is answer(-1*-2*-3 in [-1,-2,3,-4,-5]).

for simplicity of question we can merge 1st and 3rd case.
find 3 maximum elements of array, similarly find 2 minimum elements of array.
u will get 2 candidates. Print the maximum of those candidates.

C++ Code:
#include <iostream>
#include <limits.h>
using namespace std;

int main() 
{
    int n;  cin>>n;     int arr[n];     for(int a=0;a<n;a++)     cin>>arr[a];
    bool flag=0;
    int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN;
    int min1=INT_MAX,min2=INT_MAX;

    for(int a=0;a<n;a++)
    {
        if(arr[a]>max1)     {max3=max2;     max2=max1;      max1=arr[a];}
   else if(arr[a]>max2)     {max3=max2;     max2=arr[a];}
   else if(arr[a]>max3)     max3=arr[a];    flag=1;


        if(arr[a]<min1)     {min2=min1;     min1=arr[a];}
   else if(arr[a]<min2)     min2=arr[a];
    }    

    int prod1=INT_MIN,prod2=INT_MIN;
    if(max1>INT_MIN && max2>INT_MIN && max3>INT_MIN)    prod1=max1*max2*max3;
    if(max1>INT_MIN && min1<INT_MAX && min2<INT_MAX)    prod2=max1*min1*min2;

    cout<<max(prod1,prod2)<<endl;                                                
}

Answer 3

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.

Answer 4

Language - C#

Greedy Approach

Time Complexity O(n)

 public static int GetHighestProductOfThree(int[] arrayOfInts)
        {

            if (arrayOfInts.Length < 3)
            {
                throw new ArgumentException("Array should be atleast 3 items", nameof(arrayOfInts));
            }

            int highest = Math.Max(arrayOfInts[0], arrayOfInts[1]);
            int lowest = Math.Min(arrayOfInts[0], arrayOfInts[1]);

            int highestProductOf2 = arrayOfInts[0] * arrayOfInts[1];
            int lowestProductOf2 = arrayOfInts[0] * arrayOfInts[1];

            int highestProductOf3 = arrayOfInts[0] * arrayOfInts[1] * arrayOfInts[2];

            for (int i = 2; i < arrayOfInts.Length; i++)
            {
                int current = arrayOfInts[i];
                highestProductOf3 = Math.Max(Math.Max(
                    highestProductOf3,
                    current * highestProductOf2),
                    current * lowestProductOf2);

                highestProductOf2 = Math.Max(Math.Max(
                    highestProductOf2,
                    current * highest),
                    current * lowest);

                lowestProductOf2 = Math.Min(Math.Min(
                    lowestProductOf2,
                    current * highest),
                    current * lowest);

                highest = Math.Max(highest, current);
                lowest = Math.Min(lowest, current);
            }

            return highestProductOf3;
        }

Thanks to interviewcake.com

Detailed Explanation of this Algorithm

Answer 5

in JavaScript

function largestProduct(ints) {
    ints.sort((a, b) => b - a);
    return ints[0] * ints[1] * ints[2];
}

Answer 6

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