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

public class MaxProdofThreenumbers {
public int ThreeLargeNumbers(int[] a) {
int topfirstpos = 0;
    int topsecpos = 0;
    int topthirdpos = 0;
    int topfirstneg = 0;
    int topsecneg = 0;
    int prodneg = 0;
    int prodpos = 0;
    int prodmax = 0;
    boolean flag = false;
for (int i = 0; i < a.length; i++) {
        String num = a[i] + "";
        if (num.contains("-")) {
            String array[] = num.split("-");
            num = array[1];
            flag = true;
        } else 
            flag = false;
        if (flag) {
            if (topfirstneg < Integer.valueOf(num)) {
                topsecneg = topfirstneg;
                topfirstneg = Integer.valueOf(num);
            } else if (topsecneg < Integer.valueOf(num)) {

                topsecneg = Integer.valueOf(num);
        }
    }
        else {
            if (topfirstpos < Integer.valueOf(num)) {
                topsecpos = topfirstpos;
                topfirstpos = Integer.valueOf(num);
            }
        else if (topsecpos < Integer.valueOf(num)) {
                topthirdpos = topsecpos;
                topsecpos = Integer.valueOf(num);
            }
            else if (topthirdpos < Integer.valueOf(num)) {
                topthirdpos = Integer.valueOf(num);
            }
        }
    }
    prodneg = topfirstneg * topsecneg;
    prodpos = topfirstpos * topsecpos;

    if (prodneg > prodpos) {
        prodmax = prodneg * topfirstpos;
    } else {
        prodmax = prodpos * topthirdpos;
    }
    return prodmax;
}

public static void main(String a[]) {
    int list[] = { -29, 3, -2, -57, 8, -789, 34 };
MaxProdofThreenumbers t = new MaxProdofThreenumbers();
System.out.println(t.ThreeLargeNumbers(list));

}

}

Answer 2

 // Here is a simple java program to find the maximum product of three numbers in  an array.

import java.util.*;
import java.lang.*;

class MOHAN_BERA
{
public static void main(String[] args)
{
    Scanner s = new Scanner(System.in);
        System.out.println("enter the lenth of array:");
        int num1=s.nextInt();
        int[] num2=new int[num1];
        System.out.println("enter the numbers of array:");
        for(int i=0;i<num1;i++)
        {
            num2[i]=s.nextInt();
        }
        Arrays.sort(num2);//sort the array

        long max1=num2[num1-1]*num2[num1-2]*num2[num1-3];//Three last numbers, can be three positive numbers
        long max2=num2[num1-1]*num2[0]*num2[1];//last numbers and first two numbers,can be first two negetive and last one positive numbers
        long max3=num2[0]*num2[1]*num2[2];//for all negetives numbers

        long max=max1;//max1 greatest
        if(max<max2 && max3<max2) //max2 greatest
        {
            max=max2;
        }
        else if(max<max3 && max2<max3)//max3 greatest
        {
            max=max3;
        }
        System.out.println(max);
 }
 }

Answer 3

This problem can be done in O(n) time.

Keep track of these 5 variables and update them during every iteration:

1. highest product of 3 numbers
2. highest product of 2 numbers
3. highest element
4. lowest product of 2 numbers
5. lowest element

After last iteration, product of 3 numbers variable will be the answer.

Answer 4

package interviewProblems;

import interviewProblems.exceptions.ArrayTooSmallException;
import java.util.PriorityQueue;

public class Problem5 {

    public static void main(String[] args) {

        int[] data1 = new int[]{};                                  // error
        int[] data2 = new int[]{1, 5};                              // error
        int[] data3 = new int[]{1, 4, 2, 8, 9};                     // Case: all positive --> 3-max
        int[] data4 = new int[]{10, 11, 12, -20};                   // Case: 1 negative   --> 3-max
        int[] data5 = new int[]{-5, -6, -10, 7, 8, 9};              // Case: 2+ negative  --> 3-max || 1-max 2-small
        int[] data6 = new int[]{-12, -10, -6, -4};                  // Case: all negative --> 3-max

        int[] data7 = new int[]{-10, -10, 1, 3, 2};
        try {
            productOfThree(data2);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        try {
            System.out.println(productOfThree(data3));
            System.out.println(productOfThree(data4));
            System.out.println(productOfThree(data5));
            System.out.println(productOfThree(data6));
            System.out.println(productOfThree(data7));
        } catch (Exception e) {
            System.out.println("You should not see this line");
        }

    }

    //  O(n) time
    //  O(1) memory
    private static int productOfThree(int[] data) throws ArrayTooSmallException {
        if (data.length < 3) {
            throw new ArrayTooSmallException(3 , data.length);
        }

        PriorityQueue<Integer> maxNumbers = new PriorityQueue<>();                  // keep track of 3 largest numbers
        PriorityQueue<Integer> minNumbers = new PriorityQueue<>((x, y) -> y - x);   // keep track of two smallest numbers

        for (int i = 0; i < data.length; i++) {
            maxNumbers.add(data[i]);
            minNumbers.add(data[i]);
            if(maxNumbers.size() > 3) {
                maxNumbers.poll();
            }
            if(minNumbers.size() > 2){
                minNumbers.poll();
            }
        }

        int maxLow = maxNumbers.poll();
        int maxMed = maxNumbers.poll();
        int maxHigh = maxNumbers.poll();

        int minHigh = minNumbers.poll();
        int minLow = minNumbers.poll();

        int possibleProduct1 = maxHigh * maxMed * maxLow;
        int possibleProduct2 = maxHigh * minHigh * minLow;

        return Math.max(possibleProduct1, possibleProduct2);
    }

//  O(n) time
//  O(n) memory
//    private static int productOfThree(int[] data) throws ArrayTooSmallException {
//        if(data.length < 3) {
//            throw new ArrayTooSmallException("Array must be at least 3 long to preform productOfThree(int[] data)");
//        }
//
//        PriorityQueue<Integer> maxNumbers = new PriorityQueue<>((x , y) -> y - x);    // keep track of 3 largest numbers
//        PriorityQueue<Integer> minNumbers = new PriorityQueue<>();                    // keep track of two smallest numbers
//
//        for(int i = 0; i < data.length; i++) {
//            maxNumbers.add(data[i]);
//            minNumbers.add(data[i]);
//        }
//
//        int maxHigh = maxNumbers.poll();
//        int maxMed = maxNumbers.poll();
//        int maxLow = maxNumbers.poll();
//
//        int minLow = minNumbers.poll();
//        int minHigh = minNumbers.poll();
//
//        int possibleProduct1 = maxHigh * maxMed * maxLow;
//        int possibleProduct2 = maxHigh * minHigh * minLow;
//
//        return Math.max(possibleProduct1 , possibleProduct2);
//    }

}

https://github.com/amilner42/interviewPractice/blob/master/src/interviewProblems/Problem5.java

Answer 5

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ComputeMaxProduct {
    public static void main(String[] args){

        int [] arr = {4, 5, -19, 3};

        List<Integer> superSet = new ArrayList<>();

        for (int a : arr ){
        superSet.add(a);
        }

        int k = 3;

        int maxProduct = computeMaxProduct(superSet, k);
        System.out.println("maximum product is : " + maxProduct);
    }

    private static int computeMaxProduct( List<Integer> superSet, int k ){
        List<Set<Integer>> res = getSubsets(superSet,k);
        int maxProduct = 1;
        for(int index = 0; index < res.size(); index++){
        int product = 1;
        for(Integer i : res.get(index)){
            product *= i;
        }

        if (product > maxProduct){
            maxProduct = product;
        }
        }

    return maxProduct;
    }


    private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
        //successful stop clause
        if (current.size() == k) {
            solution.add(new HashSet<>(current));
            return;
        }
        //unseccessful stop clause
        if (idx == superSet.size()) return;
        Integer x = superSet.get(idx);
        current.add(x);
        //"guess" x is in the subset
        getSubsets(superSet, k, idx+1, current, solution);
        current.remove(x);
        //"guess" x is not in the subset
        getSubsets(superSet, k, idx+1, current, solution);
    }

    public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
        List<Set<Integer>> res = new ArrayList<>();
        getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
        return res;
    }
}

Answer 6

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