Find maximum product of 3 numbers in an array

user_3011937 0
Viewed 32786

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

dynamic-programming arrays algorithm java
22 Answers

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

user_64819250

in JavaScript

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

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

user_16685010 
def solution(A):
   if len(A) < 3:
      return 0
   A.sort()
   product = A[len(A)-1] * A[len(A)-2] * A[len(A)-3]
   if A[0] < 0 and A[1] < 0:
      if A[0] * A[1] * A[len(A)-1] > product:
         product = A[0] * A[1] * A[len(A)-1]
   return product
user_112435560

Below is my solution in JavaScript:

function solution(A) {
    A = A.sort((a, b) => b - a);
    var product = A[0] * A[1] * A[2];
    var length = A.length;
    if (A[0] < 0) return product;
    if (A[length - 1] * A[length - 2] * A[0] > product) {
        return A[length - 1] * A[length - 2] * A[0];
    }
    if (A[2] < 0 && length >= 5 && A[3] * A[4] < A[0] * A[1]) {
        return A[2] * A[3] * A[4];
    }
    return product;
}

user_57725290

This Solution is applicable only if there are 3 numbers needed. If It's dynamic or say user can ask for 4 or 5 then this solution is not suitable for it.

Without sorting you can achieve it by find out max 3 numbers from array and multiply 3 numbers, because max product requires max number from array.

public class FindOutProductPair {
    public static void main(String args[]) {
        int arr[]= {2,4,3,6,12,1};
//      int arr1[]= {2,4,3,7,6,5,1};
//      int arr1[]= {-1,-4,3,7,6,5,1};
        int arr1[]= {3,2};

        int max1=1,max2=1,max3=1;
        for(int i=0;i<arr1.length;i++) {
            if(max1 < arr1[i]) {
                max3=max2;
                max2=max1;
                max1=arr1[i];
            }else {
                if(max2 < arr1[i]) {
                    max3=max2;
                    max2=arr1[i];
                }
                else {
                    if(max3< arr1[i]) {
                        max3=arr1[i];
                    }
                }
            }
        }
        System.out.println((max3+" "+max2+" "+max1)+" <-- "+(max3*max2*max1));
    }
}
user_66920710

Could be like this in JAVA:

public final static int maxProizvedenieTrexChisel(Integer m []){
Arrays.sort(m,(g,g1)->g-g1);
System.out.println(Arrays.toString(m));
        int mx1=m[0]*m[1]*m[2];
        int mx2=m[m.length-1]*m[m.length-2]*m[m.length-3];
        int mx3=m[0]*m[1]*m[m.length-1];
        if(mx1>mx2&mx1>mx3)
            return mx1;
                   else if(mx2>mx1&mx2>mx3)
                           return mx2;

        return mx3;

}
user_128732510

could be solve using 5 variables with O(n) pass.
Max Product can be formed by either:
1. Max1 * Max2 * Max3
2. Max1 * Min1 * min2
where Max is maximum element and Min stands for minimum.
Here is my Java solution:

int maxProduct(int[] arr) {
    int max1, max2, max3 = Integer.MIN_VALUE;
    max1 = max3;
    max2 = max3;
    int min1 = Integer.MAX_VAULE;
    int min2 = Integer.MAX_VAULE;
    for(int n : arr) {
        if (n <= min1) {            // n is smaller than all
            min2 = min1;
            min1 = n;
        } else if (n < min2) {     // n lies between min1 and min2
            min2 = n;
        }
        if (n >= max1) {            // n is greater than all
            max3 = max2;
            max2 = max1;
            max1 = n;
        } else if (n >= max2) {     // n lies betweeen max1 and max2
            max3 = max2;
            max2 = n;
        } else if (n > max3) {     // n lies betwen max2 and max3
            max3 = n;
        }
    }
}
user_110737690

JavaScript code

function solution(A) {
    if(A.length<3){
        return 0;
    }
    let maxElement = Number.NEGATIVE_INFINITY;
    let idx = null;
    for(let i=0;i<A.length;i++){
        if(A[i]>maxElement){
            maxElement = A[i];
            idx = i;
        }
    }

        A.splice(idx,1);
        A.sort((a,b)=>b-a);
        let n = A.length;
        let positiveMax = A[0]*A[1]*maxElement;
        let negativeMax = A[n-1]*A[n-2]*maxElement;

    return Math.max(positiveMax,negativeMax);    
}
user_111382370
Related