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

Naive Solution Requires sorting the input data & then finding product of 3 largest from the last isn't it can't we do it linear time :0

Data Structure Used: Array

Algorithm:
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.

so let l1,l2,l3 are the three maximum number & s1,s2 are the minimum numbers
Our Solution will be maxproduct=max( l1*s1*s2,l1*l2*l2)

#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;
}

Time Complexity O(N) As we Done only Single Pass Over Array
Space Complexity O(1)
Run Here https://ideone.com/4zhiE