Table of Contents
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.
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.
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.
Space Complexity
O(1) because we don’t use any auxiliary space at here.