CODEWITHSUNDEEP
arraysalgorithmsortingdata-structures
ashish2199
ashish2199

Reputation: 393

Find maximum product of element each from three Arrays

Given 3 arrays of variable lengths having integers(positive and negatives) find maximum product that can be formed by multiplying a element taken from each array.

Eg.

A = [ 10, -10,15,-12];
B = [10, -12,13,-12];
C = [-11, -10, 9,-12];

For the above arrays: Maximum product = 2160 using 15, -12, -12.

I tried to implement it using brute force approach O(N^3) using three nested for loops but I am looking for more optimized approach.

int[] A = new int[]{10,-10,15,-12};
int[] B = new int[]{10,-12,13,-12};
int[] C = new int[]{-11,-10,9,-12};

int max = Integer.MIN_VALUE;

int pos[][]=new int[3][2];

for (int i=0; i < A.length ; i++ ){

    for (int j=0; j < B.length ; j++ ){

        for (int k=0; k < C.length ; k++ ){

            int prod = A[i] * B[j] * C[k];

            if( prod > max ){
                max = prod;
                pos[0][0]=i;
                pos[1][0]=j;
                pos[2][0]=k;
                pos[0][1]=A[i];
                pos[1][1]=B[j];
                pos[2][1]=C[k];
            }

        } 
    }   
}
System.out.println("Maximum product = "+max+" using "+pos[0][1]+", "+pos[1][1]+", "+pos[2][1]+".");

My thoughts so far :

I have tried thinking of sorting the arrays but then realised we need to sort using absolute values. I then thought of using element with maxium absolute value.

But unable to go forward from here on how to choose next two to optimise the solution.

Upvotes: 1

Views: 495

Answers (3)

RobertBaron
RobertBaron

Reputation: 2854

This is very similar to How to get the K smallest Products from pairs from two sorted Arrays?, except that here we have three lists and are interested in the maximum product.

  1. Find the minimum and maximum values of each list: minA, maxA, minB, maxB, minC, and maxC.

  2. The maximum product is the maximum of:

    minA * minB * minC

    minA * minB * maxC

    minA * maxB * minC

    minA * maxB * maxC

    maxA * minB * minC

    maxA * minB * maxC

    maxA * maxB * minC

    maxA * maxB * maxC

Upvotes: 1

user448810
user448810

Reputation: 17866

There are four ways the maximum product can be formed:

  1. take the maximum from each of the three arrays
  2. take the maximum from the first array and the minimum from the second and third arrays
  3. take the maximum from the second array and the minimum from the first and third arrays
  4. take the maximum from the third array and the minimum from the first and second arrays

You can find the minimum and maximum elements by sorting or simply by scanning sequentially through the arrays.

Upvotes: 0

AbsoluteSpace
AbsoluteSpace

Reputation: 770

One option is to sort all three arrays which costs O(nlogn) time each (this isn't nested), and then place the most positive and negative elements from each of the sorted arrays into another array which you also sort for O(nlogn) time.

At this point you could just check in the 6 element array to see whether the product of the three most positive elements is greater than the product of the most positive element and the two most negative elements and return that result.

Upvotes: 1

Related Questions