**Question:**

Given an array of integers (unsigned integers > 0), find three numbers in that array which form the maximum product. [O(nlogn), O(n) solutions are available ].

int[] MaxProduct(int[] input, int size)

**Solution:**

The program expects both the solutions, one in O(n) time and the other one in O(nlogn). To achieve O(nlogn), sort the entire set by using quick sort or merge sort and take the top three values.

I have provided the code for the O(n) case. It does a single scan on the entire set of elements once and finds the largest three numbers with the logic as shown below.

//============================================================================ // Name : three_largest_elems.cpp // Author : Prabhu Jayaraman (My honorable room mate, college mate, work colleague) // Version : v1 // Copyright : open // Description : To find three largest numbers in an array in C++, Ansi-style //============================================================================ #include <iostream> using namespace std; int main() { int a[10] = {1,2,33,4,15,6,7,28,9,10}; int largest_1 = 0, largest_2 = 0, largest_3 = 0; for(int i=0;i<10;i++) { if(a[i] > largest_3 && a[i] < largest_2) { largest_3 = a[i]; } else if(a[i] > largest_2 && a[i] < largest_1) { largest_3 = largest_2; largest_2 = a[i]; } else if(a[i] > largest_1) { largest_3 = largest_2; largest_2 = largest_1; largest_1 = a[i]; } } cout << "largest :" << largest_1 << endl; cout << "2nd largest :" << largest_2 << endl; cout << "3rd largest :" << largest_3 << endl; return 0; }

Cheers!!

Bragaadeesh