Minimal product subsequence where adjacent elements are separated by a maximum distance of K | C ++ implementation of the above approach . ; Function to get the minimum product of subsequence such that adjacent elements are separated by a max distance of K ; multiset will hold pairs pair = ( log value of product , dp [ j ] value ) dp [ j ] = minimum product % mod multiset will be sorted according to log values Therefore , corresponding to the minimum log value dp [ j ] value can be obtained . ; For the first k - sized window . ; Update log value by adding previous minimum log value ; Update dp [ i ] ; Insert it again into the multiset since it is within the k - size window ; Eliminate previous value which falls out of the k - sized window ; Insert newest value to enter in the k - sized window . ; dp [ n - 1 ] will have minimum product % mod such that adjacent elements are separated by a max distance K ; Driver Code
#include <bits/stdc++.h> NEW_LINE #define mp  make_pair NEW_LINE #define ll  long long NEW_LINE using namespace std ; const int mod = 1000000007 ; const int MAX = 100005 ; int minimumProductSubsequence ( int * arr , int n , int k ) { multiset < pair < double , int > > s ; ll dp [ MAX ] ; double p [ MAX ] ; dp [ 0 ] = arr [ 0 ] ; p [ 0 ] = log ( arr [ 0 ] ) ; s . insert ( mp ( p [ 0 ] , dp [ 0 ] ) ) ; for ( int i = 1 ; i < k ; i ++ ) { double l = ( s . begin ( ) ) -> first ; ll min = ( s . begin ( ) ) -> second ; p [ i ] = log ( arr [ i ] ) + l ; dp [ i ] = ( arr [ i ] * min ) % mod ; s . insert ( mp ( p [ i ] , dp [ i ] ) ) ; } for ( int i = k ; i < n ; i ++ ) { double l = ( s . begin ( ) ) -> first ; ll min = ( s . begin ( ) ) -> second ; p [ i ] = log ( arr [ i ] ) + l ; dp [ i ] = ( arr [ i ] * min ) % mod ; multiset < pair < double , int > > :: iterator it ; it = s . find ( mp ( p [ i - k ] , dp [ i - k ] ) ) ; s . erase ( it ) ; s . insert ( mp ( p [ i ] , dp [ i ] ) ) ; } return dp [ n - 1 ] ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 2 ; cout << minimumProductSubsequence ( arr , n , k ) ; return 0 ; }