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
// Copyright   : open
// 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[3];
 int negative = 0;
 for(int i = 0; i < 3; i++)
 {
  output[i] = -999999;
 }
 int min[2] = {0,0};

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

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

 if(size != negative)
 {
  if((min[0] * min[1]) > (output[0] * output[1]) || (min[0] * min[1]) > (output[1] * output[2]))
  {
   output[1] = min[0];
   output[2] = min[1];
  }
 }

 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!
Bragaadeesh.