Maximum product of an increasing subsequence in C++

In this tutorial, we will be discussing a program to find maximum product of an increasing subsequence.

For this we will be provided with an array of integers. Our task is to find the maximum product of any subsequence of the array with any number of elements.

Example

 Live Demo

#include <bits/stdc++.h> #define ll long long int using namespace std; //returning maximum product ll lis(ll arr[], ll n) {    ll mpis[n];    //initiating values    for (int i = 0; i < n; i++)       mpis[i] = arr[i];    for (int i = 1; i < n; i++)       for (int j = 0; j < i; j++)          if (arr[i] > arr[j] && mpis[i] < (mpis[j] * arr[i]))             mpis[i] = mpis[j] * arr[i];             return *max_element(mpis, mpis + n); } int main() {    ll arr[] = { 3, 100, 4, 5, 150, 6 };    ll n = sizeof(arr) / sizeof(arr[0]);    printf("%lld", lis(arr, n));    return 0; }

Output

45000