CODEWITHSUNDEEP
javaarraysalgorithmdynamic-programming
user3011937
user3011937

Reputation: 261

Find maximum product of 3 numbers in an array

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

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

Upvotes: 13

Views: 35685

Answers (22)

Abhijit Tambe
Abhijit Tambe

Reputation: 1

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

Upvotes: 0

shibashis
shibashis

Reputation: 67

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

Upvotes: 0

Anton Romanov
Anton Romanov

Reputation: 1

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;

}

Upvotes: 0

Ravi
Ravi

Reputation: 1

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

Upvotes: 0

Cassia Hou
Cassia Hou

Reputation: 1

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

Upvotes: 0

Sumitra Barua
Sumitra Barua

Reputation: 1

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

Upvotes: 0

Jameel Moideen
Jameel Moideen

Reputation: 7931

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

Upvotes: 0

Shanu T Thankachan
Shanu T Thankachan

Reputation: 1073

in JavaScript

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

Upvotes: 0

ravi tanwar
ravi tanwar

Reputation: 618

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.

Upvotes: 2

Sailee Renapurkar
Sailee Renapurkar

Reputation: 27

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

Upvotes: 2

Mohan Bera
Mohan Bera

Reputation: 1

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

Upvotes: 0

Avinash
Avinash

Reputation: 1

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

Upvotes: -1

Sumedha Khatter
Sumedha Khatter

Reputation: 51

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

Upvotes: 5

Gautam Malhotra
Gautam Malhotra

Reputation: 21

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

Upvotes: 0

displayname
displayname

Reputation: 798

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

Upvotes: 0

tick_tack_techie
tick_tack_techie

Reputation: 429

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.

Upvotes: 0

user4259055
user4259055

Reputation: 11

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.

Upvotes: 1

Arie Milner
Arie Milner

Reputation: 316

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

Upvotes: 0

Midhula Kadiyala
Midhula Kadiyala

Reputation: 11

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

}

}

Upvotes: 1

openmike
openmike

Reputation: 272

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

Upvotes: 1

Srinath Mandava
Srinath Mandava

Reputation: 3462

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

Upvotes: 20

Scott Hunter
Scott Hunter

Reputation: 49803

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.

Upvotes: 8

Related Questions