Maximum product of an increasing subsequence | Dynamic programming C ++ implementation of maximum product of an increasing subsequence ; Returns product of maximum product increasing subsequence . ; Initialize MPIS values ; Compute optimized MPIS values considering every element as ending element of sequence ; Pick maximum of all product values ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE using namespace std ; ll lis ( ll arr [ ] , ll n ) { ll mpis [ n ] ; 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 ; }