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