Maximum product of an increasing subsequence of size 3 - GeeksforGeeks

Maximum product of an increasing subsequence of size 3 - GeeksforGeeks
Given an array of distinct positive integers, the task is to find the maximum product of increasing subsequence of size 3, i.e., we need to find arr[i]*arr[j]*arr[k] such that arr[i] < arr[j] < arr[k] and i < j < k < n

A Simple solution is to use three nested loops to consider all subsequences of size 3 such that arr[i] < arr[j] < arr[k] & i < j < k). For each such sub-sequence calculate product and update maximum product if required.

An Efficient solution takes O(n log n) time. The idea is to find following two for every element. Using below two, we find the largest product of an increasing subsequence with an element as middle element. To find the largest product, we simply multiply the element with below two.

1. Largest greater element on right side.
2. Largest smaller element on left side.

Note : We need largest of as we want to maximize the product.

To find largest element on right side, we use the approach discussed here. We just need to traverse array from right and keep track of maximum element seen so far.

To find closest smaller element, we use self-balancing binary search tree as we can find closest smaller in O(Log n) time. In C++, set implements the same and we can use it to find closest element.

long long int maxProduct(int arr[] , int n)

{

    // An array ti store  closest smaller element on left

    // side of every element. If there is no such element

    // on left side, then smaller[i] be -1.

    int smaller[n];

    smaller[0] = -1 ;// no smaller element on right side

 

    // create an empty set to store visited elements from

    // left side. Set can also quickly find largest smaller

    // of an element.

    set<int>S ;

    for (int i = 0; i < n ; i++)

    {

        // insert arr[i] into the set S

        auto j =  S.insert(arr[i]);

        auto itc = j.first; // points to current element in set

 

        --itc; // point to prev element in S

 

        // If current element has previous element

        // then its first previous element is closest

        // smaller element (Note : set keeps elements

        // in sorted order)

        if (itc != S.end())

            smaller[i] = *itc;

        else

            smaller[i] = -1;

    }

 

    // Initialize result

    long long int result = INT_MIN;

 

    // Initialize greatest on right side.

    int max_right = arr[n-1];

 

    // This loop finds greatest element on right side

    // for every element. It also updates result when

    // required.

    for (int i=n-2 ; i >= 1; i--)

    {

        // If current element is greater than all

        // elements on right side, update max_right

        if (arr[i] > max_right)

            max_right = arr[i];

 

        // If there is a greater element on right side

        // and there is a smaller on left side, update

        // result.

        else if (smaller[i] != -1)

            result = max(smaller[i] * arr[i] * max_right,

                                                result);

    }

 

    return result;

}

Read full article from Maximum product of an increasing subsequence of size 3 - GeeksforGeeks