Find increasing sub-sequence of length three having maximum product

Algorithm/Insights

The idea is - for given array 'a' and for every element a[i], find out the largest element-'leftLargest' which is less than a[i] in left sub-array from index 0 to index 'i-1', and find out the largest element-'rightLargest' which is greater than a[i] in right sub-array from index 'i+1' to 'size of array'. The product leftLargest*a[i]*rightLargest would be the largest possible product of increasing sub-sequence of three elements which includes a[i]. If for any element a[i], leftLargest or rightLargest value is not found then we set that to 0 since no triplet is possible by including this element 'a[i]' in mid-position of sequence. We find out this product(leftLargest*a[i]*rightLargest) for all 'a[i]' values and find out the maximum value from these values.    

You may want to checkout function - findSequence(int[] array, int[] sequenceIndices) for implementation details.

This algorithm runs in O(n^2) time with extra space of order O(1).

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(n^2) time.
 * @author Nilesh
 */

public class SubsequenceMaxProduct 
{
    
    private int findLeftLargest(int[] array, int index)
    {
        int maxValue = -1, maxIndex = -1;
        for (int i = 0; i < index; i++)
        {
            if ((array[i] < array[index]) && (array[i] > maxValue))
            {
                maxValue = array[i];
                maxIndex =i;
            }
        }
        
        return maxIndex;
    }
    
    private int findRightLargest(int[] array, int index)
    {
        int maxValue = -1, maxIndex = -1;
        for (int i = index+1; i < array.length; i++)
        {
            if ((array[i] > array[index]) && (array[i] > maxValue))
            {
                maxValue = array[i];
                maxIndex =i;
            }
        }
        
        return maxIndex;
    }
    
    public void findSequence(int[] array, int[] sequence)
    {
        int maxProduct = 0;
        for (int i = 0; i < array.length; i++)
        {
            // find largest element which is less than a[i] in the left sub-array
            int leftLargestIndex = findLeftLargest(array, i);
            int leftLargestValue = leftLargestIndex == -1 ? 0:array[leftLargestIndex];
            
            // find largest element greater than a[i] in the right subarray
            int rightLargestIndex = findRightLargest(array, i);
            int rightLargestValue = rightLargestIndex == -1 ? 0:array[rightLargestIndex];
            
            if (leftLargestValue*array[i]*rightLargestValue > maxProduct)
            {
                maxProduct = array[leftLargestIndex]*array[i]*array[rightLargestIndex];
                sequence[0] = leftLargestValue;
                sequence[1] = array[i];
                sequence[2] = rightLargestValue;
            }
        }
    }
    
    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(n^2)
Space Complexity is O(1)