find 3 size subseq whose product is max

ArraySumSubsequence.c++

//Max Product of three item subseq
//output 6  8  9
       //Max Prod = 432

#include<iostream>

using namespace std;

int Max(int i, int j)
{
   return i > j ? i : j;
}

int* MaxProduct(int arr[], int n)
{
   int max = arr[0];

   int *L = new int[n];
   int *R = new int[n];

   for(int i = 1; i < n; i++)
   {
      L[i] = max;
      max = Max(arr[i],max);
   }
   
   max = arr[n-1];

   for(int i = n-2; i > 0; --i)
   {
      R[i] = max;
      max = Max(arr[i],max);
   }

   max = 0;

   int *res = new int[3];

  for(int i = 1; i < n-1; ++i) //1 to n-2 check
  {
     if(arr[i] > L[i]  && arr[i] < R[i])
     {
        max = Max(max,arr[i]*L[i]*R[i]);
        res[0] = L[i];
        res[1] = arr[i];
        res[2] = R[i];
     }
  }

  return res;
}

int main()
{
    int arr[] = {6,1,3,2,8,7,3,2,9,7,5,4};

    int n = sizeof(arr)/sizeof(arr[0]);
    int* p = MaxProduct(arr,n);

    if(p != NULL)
    {
        cout<<p[0]<<"  "<<p[1]<<"  "<<p[2]<<endl;
        cout<<"Max Prod = "<<p[0]*p[1]*p[2];
        delete p;
    }
    return 0;
}

This code i updated for better complexity now i using avl tree to find just lesser element in left side....right side we using highest element that is greater than curr so that side no change now we doing this problem in nlogn time and this fully contributed by avl tree ...

for correct solution check my gits update.....

https://gist.github.com/satveersm/89acbd6a2a8b9f02b617