Increasing Subsequence of Length three with Maximum Product  

Difficulty Level Easy
Frequently asked in Amazon Apple Cisco Citadel Facebook Intuit Uber
Array Redfin

Problem Statement  

In the “Increasing Subsequence of Length three with Maximum Product” problem, we have given an array of positive integers. Find the subsequence of length 3 with the maximum product. Subsequence should be increasing.

Input Format  

The first and only one line containing an integer N denoting the size of the given array.

Second-line containing N space-separated integers.

Output Format  

The first and only one line containing 3 integers if there is a subsequence of length 3 with the maximum_product and subsequence is in increasing order. Otherwise, print -1.

Please click Like if you loved this article?

Constraints  

  • 1<=N<=10^3
  • -10^9<=a[i]<=10^9

Example  

8
11 12 13 6 7 8 14 15
13 14 15

Explanation:  [13, 14, 15] is a subsequence of length 3 with the maximum product.

5
5 4 3 2 1
-1

Explanation:  No such subsequence of length 3 which is increasing in order.

Algorithm  

LSL – largest smallest element on the left.
LGR – largest greater element on the right.

a. For all the elements we need to find the largest smaller element(LSL) on the left of it and the largest greater element on the right(LGR).

b. We run two nested loops. One is to find LGR and LSL.

See also
Can Make Arithmetic Progression From Sequence Leetcode Solution

c. The maximum of the product of LGR, LSL, and number will be the largest increasing subsequence of length 3 with the maximum product.

Implementation  

C++ Program for Increasing Subsequence of Length three with Maximum Product

#include <bits/stdc++.h>
using namespace std;


int FindLSL(int array[], int index, int n)
{
    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;
}

int FindLGR(int array[], int index, int n)
{
    int maxValue = -1, maxIndex = -1;
    for (int i = index+1; i < n; i++)
    {
        if ((array[i] > array[index]) && (array[i] > maxValue))
        {
            maxValue = array[i];
            maxIndex =i;
        }
    }
    
    return maxIndex;
}

void FindSequence(int array[], int sequence[3], int n)
{
    int maxProduct = 0;
    for(int i = 0; i < n ; i++)
    {
        int leftLargestIndex = FindLSL(array, i,n);
        int leftLargestValue = leftLargestIndex == -1 ? 0:array[leftLargestIndex];
        int rightLargestIndex = FindLGR(array, i,n);
        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;
        }
    }
}

int main()
{ 
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sequence[3];
    for(int i=0;i<3;i++)
    {
        sequence[i]=-1000000;
    }
    FindSequence(a,sequence,n);
    int flag=0;
    for(int i=0;i<3;i++)
    {
        if(sequence[i]==-1000000)
        {
            flag=1;
        }
    }
    if(flag==1)
    {
        cout<<-1<<endl;
    }
    else{
    for (int i = 0; i < 3; i++)
    {
        cout<<sequence[i]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

Java Program for Increasing Subsequence of Length three with Maximum Product

import java.util.Random;
import java.util.Scanner;
class sum
{
    public static int FindLSL(int array[], int index, int n)
    {
        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;
    }

    public static int FindLGR(int array[], int index, int n)
    {
        int maxValue = -1, maxIndex = -1;
        for (int i = index+1; i < n; i++)
        {
            if ((array[i] > array[index]) && (array[i] > maxValue))
            {
                maxValue = array[i];
                maxIndex =i;
            }
        }

        return maxIndex;
    }

    public static void FindSequence(int array[], int sequence[], int n)
    {
        int maxProduct = 0;
        for(int i = 0; i < n ; i++)
        {
            int leftLargestIndex = FindLSL(array, i,n);
            int leftLargestValue = leftLargestIndex == -1 ? 0:array[leftLargestIndex];
            int rightLargestIndex = FindLGR(array, i,n);
            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)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sequence[] = new int[3];
        for(int i=0;i<3;i++)
        {
            sequence[i]= -1000000;
        }
        FindSequence(a,sequence,n);
        int flag=0;
        for(int i=0;i<3;i++)
        {
            if(sequence[i]==-1000000)
            {
                flag=1;
            }
        }
        if(flag==1)
        {
            System.out.println(-1);
        }
        else{
        for(int i=0;i<3;i++)
        {
            System.out.print(sequence[i]+" ");
        }
        System.out.println();
        }
    }
}
5
72 24 12 -10 -16
-1

Complexity Analysis  

Time Complexity

O(n^2) where n is the size of the given array. Here we find largest smallest element on the left, largest greater element on the right at every position(ith) of array which take linear time to find out.

See also
Best Time to Buy and Sell Stock  II Leetcode Solution

Space Complexity

O(1) because we don’t use any auxiliary space at here.

Please click Like if you loved this article?