Maximum product of an increasing subsequence in C++
https://www.tutorialspoint.com/maximum-product-of-an-increasing-subsequence-in-cplusplus
-
10-09-2020 - |
Question
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
#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
Not affiliated with Tutorialspoint