## 03 May 2010

### Find three numbers in an array which forms a maximum product (for signed integers)

This is a problem that we had already seen. But it gives more kick if the input has negative elements and zero!!!

Question:
Given an array of integers (signed integers), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].
int[] MaxProduct(int[] input, int size)

The solution involves in finding three maximum and two minimum numbers. If the minimum numbers are negatives and if their product is greater than the two maximum number's product, then they have to considered for maximum product. Handling all these scenarios with comprehensive test cases, please find the code below for the problem implemented in C++

```//============================================================================
// Name        : three_largest_elems.cpp
// Author      : Prabhu Jayaraman
// Version     : v2
// Description : To find three signed numbers in an array with max product
//========================================================a====================

#include <iostream>
using namespace std;

#define MAX 10

int* MaxProduct(const int input[], const int size)
{
int* output = new int;
int negative = 0;
for(int i = 0; i < 3; i++)
{
output[i] = -999999;
}
int min = {0,0};

for(int i=0;i<size;i++)
{
// find two smallest negative numbers
if(input[i] <= 0)
{
if(input[i] < min)
{
min = min;
min = input[i];
}
else if(input[i] < min)
{
min = input[i];
}
negative++;
}

// find three largest positive numbers
if(input[i] > output)
{
output = output;
output = output;
output = input[i];
}
else if(input[i] > output)
{
output = output;
output = input[i];
}
else if(input[i] > output)
{
output = input[i];
}
}

if(size != negative)
{
if((min * min) > (output * output) || (min * min) > (output * output))
{
output = min;
output = min;
}
}

return output;
}

int main()
{
const int input[MAX] = {-6,-1,-2,-33,-4,-15,-7,-28,-9,-10};
int* result = 0;
result = MaxProduct(input,MAX);

for(int i = 0; i < 3; i++)
{
cout << (i+1) << "# element : " << result[i] << endl;
}

const int input1[MAX] = {0,-1,-2,-33,4,15,-7,-28,-9,-10};
int* result1 = 0;
result1 = MaxProduct(input1,MAX);

for(int i = 0; i < 3; i++)
{
cout << (i+1) << "# element : " << result1[i] << endl;
}

const int input2[MAX] = {0,-1,-2,-33,-4,-15,-7,-28,-9,-10};
int* result2 = 0;
result2 = MaxProduct(input2,MAX);

for(int i = 0; i < 3; i++)
{
cout << (i+1) << "# element : " << result2[i] << endl;
}

const int input3[MAX] = {6,1,2,33,4,15,7,28,9,10};
int* result3 = 0;
result3 = MaxProduct(input3,MAX);

for(int i = 0; i < 3; i++)
{
cout << (i+1) << "# element : " << result3[i] << endl;
}

return 0;
}```

Cheers!

Sreekanth said...

Hi Brgadeesh i can we can use this algo its simple
static int getMaxProduct(int x[]){
Arrays.sort(x);
if(x[x.length-1]>0){
}else{
}

}

BragBoy said...

@Sreekanth: Thanks for reading and replying. Although your solution is right in all ways, the speed of it is O(nlogn). The simple reason being the Arrays.sort(x). Just because a program has more lines of code does not mean that its not fast.

Arrays.sort(x) does a quick sort within which is going to scale or increase nlogn times for each n. Whereas the solution that I've provided does the job in O(5n) = O(n) time. You can try it yourself for a huge data set.

Thanks,