Maximum product of an increasing subsequence
Given an array of numbers, find the maximum product formed by multiplying numbers of an increasing subsequence of that array.
Note: A single number is supposed to be an increasing subsequence of size 1.
Examples:
Input : arr[] = { 3, 100, 4, 5, 150, 6 } Output : 45000 Maximum product is 45000 formed by the increasing subsequence 3, 100, 150. Note that the longest increasing subsequence is different {3, 4, 5, 6} Input : arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 } Output : 21780000 Maximum product is 21780000 formed by the increasing subsequence 10, 22, 33, 50, 60.
Prerequisite : Longest Increasing Subsequence
Approach: Use a dynamic approach to maintain a table mpis[]. The value of mpis[i] stores product maximum product increasing subsequence ending with arr[i]. Initially all the values of increasing subsequence table are initialized to arr[i]. We use recursive approach similar to LIS problem to find the result.
Implementation:
C++
/* Dynamic programming C++ implementation of maximum product of an increasing subsequence */ #include <bits/stdc++.h> #define ll long long int using namespace std; // Returns product of maximum product increasing // subsequence. ll lis(ll arr[], ll n) { ll mpis[n]; /* Initialize MPIS values */ for ( int i = 0; i < n; i++) mpis[i] = arr[i]; /* Compute optimized MPIS values considering every element as ending element of sequence */ 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]; /* Pick maximum of all product values */ return *max_element(mpis, mpis + n); } /* Driver program to test above function */ int main() { ll arr[] = { 3, 100, 4, 5, 150, 6 }; ll n = sizeof (arr) / sizeof (arr[0]); printf ( "%lld" , lis(arr, n)); return 0; } |
Java
/* Dynamic programming Java implementation of maximum product of an increasing subsequence */ import java.util.Arrays; import java.util.Collections; class GFG { // Returns product of maximum product // increasing subsequence. static int lis( int [] arr, int n) { int [] mpis = new int [n]; int max = Integer.MIN_VALUE; /* Initialize MPIS values */ for ( int i = 0 ; i < n; i++) mpis[i] = arr[i]; /* Compute optimized MPIS values considering every element as ending element of sequence */ 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]; /* Pick maximum of all product values using for loop*/ for ( int k = 0 ; k < mpis.length; k++) { if (mpis[k] > max) { max = mpis[k]; } } return max; } // Driver program to test above function static public void main(String[] args) { int [] arr = { 3 , 100 , 4 , 5 , 150 , 6 }; int n = arr.length; System.out.println(lis(arr, n)); } } // This code is contributed by parashar. |
Python3
# Python program implementation # of maximum product of an increasing # Returns product of maximum product # increasing subsequence. import sys def lis(arr, n): mpis = [] Max = - sys.maxsize - 1 # Initialize MPIS values * for i in range (n): mpis.append(arr[i]) # Compute optimized MPIS values # considering every element as ending # element of sequence for i in range ( 1 ,n): for j in range (i): if (arr[i] > arr[j] and mpis[i] < (mpis[j] * arr[i])): mpis[i] = mpis[j] * arr[i] # Pick maximum of all product values # using for loop for k in range ( len (mpis)): if (mpis[k] > Max ): Max = mpis[k] return Max # Driver Code arr = [ 3 , 100 , 4 , 5 , 150 , 6 ] n = len (arr) print (lis(arr, n)) # This code is contributed by shinjanpatra |
C#
/* Dynamic programming C# implementation of maximum product of an increasing subsequence */ using System; using System.Linq; public class GFG { // Returns product of maximum product // increasing subsequence. static long lis( long [] arr, long n) { long [] mpis = new long [n]; /* Initialize MPIS values */ for ( int i = 0; i < n; i++) mpis[i] = arr[i]; /* Compute optimized MPIS values considering every element as ending element of sequence */ 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]; /* Pick maximum of all product values */ return mpis.Max(); } /* Driver program to test above function */ static public void Main() { long [] arr = { 3, 100, 4, 5, 150, 6 }; long n = arr.Length; Console.WriteLine(lis(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?PHP /* Dynamic programming PHP implementation of maximum product of an increasing subsequence */ // Returns product of maximum product increasing // subsequence. function lis(& $arr , $n ) { $mpis = array_fill (0, $n , NULL); /* Initialize MPIS values */ for ( $i = 0; $i < $n ; $i ++) $mpis [ $i ] = $arr [ $i ]; /* Compute optimized MPIS values considering every element as ending element of sequence */ for ( $i = 1; $i < $n ; $i ++) for ( $j = 0; $j < $i ; $j ++) if ( $arr [ $i ] > $arr [ $j ] && $mpis [ $i ] < ( $mpis [ $j ] * $arr [ $i ])) $mpis [ $i ] = $mpis [ $j ] * $arr [ $i ]; /* Pick maximum of all product values */ return max( $mpis ); } /* Driver program to test above function */ $arr = array ( 3, 100, 4, 5, 150, 6 ); $n = sizeof( $arr ) / sizeof( $arr [0]); echo lis( $arr , $n ); return 0; ?> |
Javascript
<script> // JavaScript program implementation of maximum product of an increasing // Returns product of maximum product // increasing subsequence. function lis(arr, n) { let mpis = []; let max = Number.MIN_VALUE; /* Initialize MPIS values */ for (let i = 0; i < n; i++) mpis[i] = arr[i]; /* Compute optimized MPIS values considering every element as ending element of sequence */ for (let i = 1; i < n; i++) for (let j = 0; j < i; j++) if (arr[i] > arr[j] && mpis[i] < (mpis[j] * arr[i])) mpis[i] = mpis[j] * arr[i]; /* Pick maximum of all product values using for loop*/ for (let k = 0; k < mpis.length; k++) { if (mpis[k] > max) { max = mpis[k]; } } return max; } // Driver Code let arr = [ 3, 100, 4, 5, 150, 6 ]; let n = arr.length; document.write(lis(arr, n)); // This code is contributed by chinmoy1997pal. </script> |
Output
45000
Time Complexity: O(n^2)
Auxiliary Space : O(n)
Contact Us