Find increasing sub-sequence of length three having maximum product | Optimized approach

Given an array of positive numbers, find sub-sequence of length three having maximum product. The elements of sub-sequence should be in increasing order. For example, for input array {6, 1, 2, 3, 19, 10, 7} output sub-sequence should be 2, 3, 19. For the input array {8, 9, 5, 1, 10, 3, 12} output should be sub-sequence 9, 10, 12.

In this post we have discussed an algorithm which runs in O(n^2) time. In this post, we will discuss an optimized algorithm which runs in O(nlogn) time.


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

For every element a[i] in array 'a', we need to find the largest element less than a[i](say leftLargest[i]) in left sub-array a[0 .. i-1] and largest element greater than a[i](say rightLargest[i]) in right sub-array a[i+1 .. lengthOfArray-1]. Once we have leftLargest[i] and rightLargest[i], we know that no increasing sequence of length 3 with a[i] as the second element in it would yield greater value for product than sequence leftLargest[i],a[i],rightLargest[i]. We compute this product leftLargest[i]*a[i]*rightLargest[i] for all elements in array 'a' and pick the maximum of these products to return the sequence which produces this maximum product.

Now let's see how can we compute leftLargest[i] and rightLargest[i] for all elements in array 'a'.
1. To compute leftLargest[i] for an element a[i], we make use of AVL tree to compute floor for each element. Floor of an element 'n' for a given array is the largest value in the given array which is less than element 'n'. After computing floor of an element a[i], a[i] is inserted into the AVL tree. If floor of a[i] is not found then leftLargest[i] is made 0. This step takes O(nlogn) time.

We have discussed how to calculate floor of an element in this post. Please note that floor definition here is slightly different than in the post because here we are looking for sequence which is strictly increasing. Checkout function getFloor() in the code snippet below which implements this functionality.

2. To compute rightLargest[i] for an element a[i], we start traversing the array from rightmost end(from index arrayLength-1). While traversing the array, we keep track of the largest element seen so far(say 'rightLargestSofar') in sub-array a[i+1 .. (arrayLength-1)]. If the value 'rightLargestSofar' is greater than a[i] then rightLargest[i] is assigned a value 'rightLargestSofar' otherwise it's assigned the value as 0; also 'rightLargestSofar' is updated to a[i]. In this way, complete array rightLargest is computed. This step takes O(n) time. Checkout function fillRightGreatest(int[] array, int[] rightGreatest) for implementation details.
  
3. After computing leftLargest[i], rightLargest[i] for all a[i]'s , we pick the maximum of products leftLargest[i]*a[i]*rightLargest[i] to output the required sequence. This step takes O(n) time. Please checkout function - findSequence(int[] array, int[] sequenceIndices) for implementation details.

Overall time complexity of this algorithm is O(nlogn) which comes from step #1 while computing 'leftLargest' array. Extra space required is O(n).


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Finds increasing sub-sequence of length three having maximum product
 * runs in O(nlogn) time. Uses AVL trees.
 * @author Nilesh
 */

public class SubsequenceMaxProduct 
{
    final static int INVALID_VALUE = -1;
    class AVLTree 
    {
        // final static int INVALID_VALUE = -1;
        private class AVLTreeNode 
        {
            int data;
            AVLTreeNode left;
            AVLTreeNode right;
            int height;
            
            AVLTreeNode(int data)
            {
                this.data = data;
                this.height = 1;
            }
        }
        
        AVLTreeNode root;
        
        AVLTree(int rootValue)
        {
            this.root = new AVLTreeNode(rootValue);
        }
        
        public AVLTree() 
        {
            
        }

        int getHeight(AVLTreeNode node)
        {
            if (node == null)
                return 0;
            
            return node.height;
        }
        
        void updateHeight(AVLTreeNode node)
        {
            if (node == null) return;
            
            node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        }
        
        
        AVLTreeNode rotateRight(AVLTreeNode node)
        {
            if (node == null) return node;
            
            AVLTreeNode beta  = node.left;
            
            AVLTreeNode t2  = beta.right;
            
            beta.right = node;
            node.left = t2;
            
            // we first need to update the height of node because height of beta uses height of node
            updateHeight(node);
            
            // now we update height of beta
            updateHeight(beta);
            
            return beta;
        }
        
        
        AVLTreeNode rotateLeft(AVLTreeNode node)
        {
            if (node == null) return node;
            
            AVLTreeNode beta  = node.right;
            AVLTreeNode t2  = beta.left;
            
            beta.left = node;
            node.right = t2;
            
            // we first need to update the height of node because height of beta uses height of node
            updateHeight(node);
            
            // now we update height of beta
            updateHeight(beta);
            
            return beta;
        }
        
        
        int getBalance(AVLTreeNode node)
        {
            if (node == null)
            {
                return 0;
            }
            int balance;
            
            balance = getHeight(node.left) - getHeight(node.right);
            
            return balance;
        }
        
        
        int getMinValue(AVLTreeNode node)
        {
            // though this case should not be hit ever for the usecase this function is employed for
            if (node == null) return Integer.MIN_VALUE;
            
            // if this is the left-most node
            if (node.left == null) return node.data;
            
            return getMinValue(node.left);
        }
        
        int getFloor(AVLTreeNode currentNode, int key)
        {
            if (currentNode == null)
            {
                return INVALID_VALUE; 
            }
            
            int floor;
            
            // if currentNode is less than key then we might find floor in right sub-tree
            // if found, return else return currentNode value
            if (currentNode.data < key)
            {
                floor = getFloor(currentNode.right, key);
                if (floor == INVALID_VALUE)
                {
                    return currentNode.data;
                }
            }
            else // if currentNode is greater than or equal to key, we must search in left sub-tree
            {
                floor = getFloor(currentNode.left, key);
            }
            return floor;
        }
        
        int getFloor(int key)
        {
            return getFloor(root, key);
        }
        
        private AVLTreeNode insert(AVLTreeNode node, int key)
        {
            // do usual BST insertion first
            if (node == null)
            {
                return new AVLTreeNode(key);
            }
            
            if (key < node.data)
            {
                node.left = insert(node.left, key);
            }
            else if (key > node.data)
            {
                node.right = insert(node.right, key);
            }
            else
            {
                return node;
            }
            
            // now update the height of the node
            updateHeight(node);
            
            // check the balance at this node and perform rotations accordingly
            int balance = getBalance(node);
            
            if (balance > 1) // indicates either left-left or left-right case
            {
                if (key < node.left.data) // confirms left-left case
                {
                    node = rotateRight(node);
                }
                else // confirms left-right case
                {
                    node.left = rotateLeft(node.left);
                    node = rotateRight(node);
                }
            }
            
            else if (balance < -1) // indicates either right-right or right-left case
            {
                if (key > node.right.data) // confirms right-right case
                {
                    node = rotateLeft(node);
                }
                else // confirms right-left case
                {
                    node.right = rotateRight(node.right);
                    node = rotateLeft(node);
                }
            }
            return node;
        }
        
        public void insert(int key)
        {
            root = insert(this.root, key);
            return;
        }
        
    }
    
    private void fillLeftGreatest(int[] array, int[] leftGreatest)
    {
        AVLTree tree = new AVLTree();
        for (int  i = 0; i < array.length; i++)
        {
            int floor = tree.getFloor(array[i]);
            if (floor == INVALID_VALUE)
            {
                leftGreatest[i] = 0;
            }
            else
            {
                leftGreatest[i] = floor;
            }
            tree.insert(array[i]);
        }
    }
    
    private void fillRightGreatest(int[] array, int[] rightGreatest)
    {
        int maxValueToRight = array[array.length-1];
        rightGreatest[array.length-1] = 0;
        
        for (int i = array.length-2; i >= 0; i--)
        {
            if (array[i] > maxValueToRight)
            {
                rightGreatest[i] = 0;
                maxValueToRight = array[i];
            }
            else
            {
                rightGreatest[i] = maxValueToRight;
            }
        }
    }
    
    public void findSequence(int[] array, int[] sequence)
    {
        int[] leftGreatest = new int[array.length];
        int[] rightGreatest = new int[array.length];
        
        fillLeftGreatest(array, leftGreatest);
        fillRightGreatest(array, rightGreatest);
        
        int maxProduct = 0;
        for (int i = 0; i < array.length-1; i++)
        {
            if ((leftGreatest[i]*array[i]*rightGreatest[i]) > maxProduct)
            {
                maxProduct = leftGreatest[i]*array[i]*rightGreatest[i];
                sequence[0] = leftGreatest[i];
                sequence[1] = array[i];
                sequence[2] = rightGreatest[i];
            }
        }
    }
    
    public static void main(String[] args) 
    {
        SubsequenceMaxProduct solution = new SubsequenceMaxProduct(); 
        
        int[] testArray =  {6, 1, 2, 3, 19, 10, 7};
        
        int[] sequence = new int[3]; 
        solution.findSequence(testArray,sequence);
        
        System.out.println("Increasing Sub-sequence of which would yield maximum product is: " );
        for (int i = 0; i < sequence.length; i++)
        {
            System.out.print(sequence[i] + ", ");
        }
    }
}
		

Order of the Algorithm

Time Complexity is O(nlogn)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer