CareerCup

find max element - o(n)
find 2nd max -o(n)
find 3rd max -o(n)

//only when array contains negative elements ...
find 1st min -o(n)
find 2nd min -o(n)

if 1stMin*2ndMin < 2ndMax*3rdNax
answer = 1stMax*2ndMax*3rdMax

else
answer = 1stMax*1stMin*2ndMin

sort by abs;
if (all negative ) product of three smallest
traverse largest to lowest, keep count of neg & non-neg (may wanna store first three pos numbers and three neg numbers); once count_neg>=0 && count_pos>=3 || count_neg>=2 && count_pos>=1 .. you know what to do

int NMaxProduct(vector<int> v,int k)
{
	int product = 1;
	partial_sort(v.begin(),v.begin()+k ,v.end ());	
	for(int i=0;i<k;i++)
		product*=v.at(i);
	return product;
}

heap1 = max-heap of all +ve numbers
heap2 = min-heap of all -ve numbers
find two products p1, p2
p1 = product of top three of heap1
p2 = product of top two of heap2 and top of heap1
take max(p1, p2)

@Anonymous
There is also one more case where there are 2 positive numbers and others are negative. Then maximum could either be product of 2 positive and maximum negative or top three of min-heap of all -ve numbers..

run selection ( median of median) algorithm 3 times with n, n-1, n-2 and find the product of the 3. O(3n) = O(n).

What if we build a min heap of 3 elements.. Once the first three elements are inserted, we should check if the next number is greater than the root of the heap in which case replace the root with the next number and perform downheap to restructure the heap. In the end we will have the greatest 3 elements in the heap. This should take n*O(logk) where k (in this case 3) is the number of elements whose product is the maximum.

Using selection algo is also a good approach, but may be degenerative if the list is sorted.

am giving the worst case solution of O(n)..( its really worse :( but it works )
Dynamic programming..
1. find the max product with 1 element involving each element.. (the elements themselves)
2. max product with two elements for each element..
3. max product with three elemnts (use the results of previous step - memoization)
the max val of last step gives the max product..

Find 3 maximum and minimum numbers.
Let them name nMax1, nMax2, nMax3, nMin1, nMin2 and nMin3 respectively.

maximum product is <- max(nMax1 * nMax2 * nMax3, nMin1 * nMin2, * nMax1)