Table of Contents

## In the given array of positive integers, find the subsequence of length 3 with maximum product

Subsequence should be increasing.

### Example

Input array: [11, 12, 13, 6, 7, 8, 14, 15]

Output: [13, 14, 15]

This is subsequence of length 3 with maximum poduct.

## Algorithm

**Time complexity: O(n2)**

LSL: largest smallest element on the left

LGR: largest greater element on the right

**a.** For all the elements we need to find largest smaller element(LSL) on the left of it and 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 maximum product.

### Algorithm working

## C++ Program

#include <bits/stdc++.h> using namespace std; //function to find Largest small element on left //search left part i.e 0 to index 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; } //function to find Largest greater element on right //search right part i.e index to last 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; } //function to find Increasing Sub-sequence of which would yield maximum product //store it in sequence array 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 testArray[] = {11, 12, 13, 6, 7, 8, 14,15}; int N = sizeof(testArray)/sizeof(int); int sequence[3]; FindSequence(testArray,sequence, N); cout<<"Increasing Sub-sequence of which would yield maximum product is: "<<endl; for (int i = 0; i < 3; i++) { cout<<sequence[i]<<", " ; } return 0; }