MaxProduct3UsingAVL

                            PAGE - 1

//AVL TREE
//MAX  PRODUCT SUBSEQ OF SIZE 3 IN INCREASING ORDER
#include<iostream>

using namespace std;

struct Node
{
   int data;
   int h;
   Node* left;
   Node* right;

   public:
   Node(int d,Node* l = NULL, Node* r = NULL)
   {
      data = d;
      h = 0;
      left = l;
      right = r;
   }
};

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

int Height(Node* root)
{

   if(root == NULL) return -1;
   return root->h;
}


//          y     2               x
//         /                     / \
//        x       1  ===>      T1   y
//       /\                         /
//     T1  T2     0               T2
//

Node* leftRotate(Node* y)
{

   Node* x = y->right;
   Node* t2 = x->left;

   x->left  = y;
   y->right = t2;

   y->h  = Max(Height(y->left),Height(y->right)) + 1;
   x->h  = Max(Height(x->left),Height(x->right)) + 1;
   return x;
}

//     y         2                x
//      \                        / \
//       x       1  ===>        y   T2
//      / \                      \
//     T1  T2    0                T1

Node* rightRotate(Node* y)
{
   Node* x = y->left;
   Node* t2 = x->right;

   x->right = y;
   y->left = t2;

   y->h = Max(Height(y->left),Height(y->right)) + 1;
   x->h = Max(Height(x->left),Height(x->right)) + 1;

   return x;
}


Node* Insert(Node* root, int k, int &ceil)
{
   if(root == NULL)
   {
      return new Node(k,NULL,NULL);
   }

   if(root->data < k)
   {
      ceil = root->data;
      root->right = Insert(root->right,k,ceil);
   }
   else if(root->data > k)
   {
      root->left = Insert(root->left,k,ceil);
   }
   else
   {
       return root;
   }

    root->h = Max(Height(root->left),Height(root->right)) + 1;

   if(Height(root->left) > Height(root->right))
   {
      if((Height(root->left) - Height(root->right)) > 1)
      {
          //check left left or left right case here
          if(root->left->data > k)//Left - left case
          {
             return rightRotate(root);
          }
          else
          {
             root->left = leftRotate(root->left);
             return rightRotate(root);
          }
      }
   }
   else if(Height(root->left) < Height(root->right))
   {

      if((Height(root->right) - Height(root->left)) > 1)
      {
          if(root->right->data < k)
          {
              return leftRotate(root);
          }
          else
          {
              root->right = rightRotate(root->right);
              return leftRotate(root);
          }
      }
   }

   return root;
}

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

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


   Node* root = new Node(arr[0],NULL,NULL);

   for(int i = 1; i < n; i++)
   {
       int ceil = 0;
       root = Insert(root,arr[i],ceil);
       L[i] = ceil;
   }

   max = arr[n-1];

   for(int i = n-2; i > 0; --i)
   {
      if(R[i] < max)
      {
          R[i] = max;
      }
      else
      {
          R[i] = 0;
      }
      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])
     {

        if(max < arr[i]*L[i]*R[i])
        {
           res[0] = L[i];
           res[1] = arr[i];
           res[2] = R[i];
           max = arr[i]*L[i]*R[i];
        }
     }
  }

  return res;
}

void Print(Node* root)
{
    if(root == NULL) return;

    Print(root->left);

    cout<<root->data<<"  ";

    Print(root->right);

}
int main()
{
    int arr[] = {6,1,3,2,8,7,9,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;
}