1
int arr[] = {10, 10, 1, 3};

Assumptions: Assume every int is positive. Assume array contains at least 3 ints

Find the highest product you can get from three of the integers in the above array. We should return 300 (which we get by taking 10 ∗ 10 ∗ 3).

I want to solve this using brute force method. Basically, I want to multiply each integer by each other integer, and then multiply that product by each other other integer. Can anyone show me how this can be done using nested 3 loops because I want to learn how it's done using brute force first before trying the optimized approach.

Thanks.

M Garp
  • 195
  • 1
  • 15
  • 5
    Why not sorting the array and using the 3 largest values after sorting? – Anonymous Jun 19 '17 at 10:35
  • What is the possible range? Can any element be negative? Can an element be zero? – Bathsheba Jun 19 '17 at 10:36
  • 1
    @YCF_L: Will not work well if negatives and zero are allowed. Currently the question is unanswerable. – Bathsheba Jun 19 '17 at 10:36
  • I have edited my questions. Hope it makes more sense now – M Garp Jun 19 '17 at 10:39
  • @MGarp: Thanks for the edit. It's *much* simpler if the `int`s are all positive. Downvote converted to upvote. – Bathsheba Jun 19 '17 at 10:39
  • 2
    @Anonymous why sort when it can be solved in O(n) time and O(1) extra space? – גלעד ברקן Jun 19 '17 at 10:44
  • 2
    Someone should probably just post the brute force solution as an answer to [Find maximum product of 3 numbers in an array](https://stackoverflow.com/questions/20550037/find-maximum-product-of-3-numbers-in-an-array) and then we can close this as a duplicate and have all the solutions to this problem in one place, because one solution here, a few solutions somewhere else and some more elsewhere doesn't make much sense. – Bernhard Barker Jun 19 '17 at 11:04
  • Side sigh: *"Assume every int is positive"* spoils all the fan: the right question should be "an array with length >= 3 with **arbitrary** int's...". Negative , zero items and integer overflow (when multiplying) will make the problem its charm. And, of course, `O(N)` complexity – Dmitry Bychenko Jun 19 '17 at 11:26

2 Answers2

3

Using three for loops : 

public static Integer highestProduct(int array[]) 
{
    if((array==null)||(array.length<3))
    {
        return null;
    }

    else
    {
        int max_product = Integer.MIN_VALUE;
        for(int i=0;i<array.length;i++)
        {
            for(int j=i+1;j<array.length;j++)
            {
                for(int k=j+1;k<array.length;k++)
                {
                    int product = array[i]*array[j]*array[k];
                    if(product>=max_product)
                    {
                        max_product = product;
                    }
                }
            }
        }
        return max_product;
     }
 }
Gwaldhorf Miopau
  • 125
  • 10
2

there are some solutions to ignore brute force.

1. Sort

First you can sort array, it takes O(nlogn) time. After sorting select last 3 items. As they are highest items, then product will maximum

NOTE: It will not work if there are any negative numbers in your array. For fixing it you can check some combinations. First calculate first 3 items product, then last 3, then First 2 and Last 1. One of these will be greatest.

2. Dynamic programming

Please see matrix chain multiplication or max growing length problems and dynamic programming solutions for them. It will help you to understand what is dynamic programming and create simple algorithm to solve your problem.

Gor
  • 2,808
  • 6
  • 25
  • 46