Minimal product subsequence where adjacent elements are separated by a maximum distance of K | Python3 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
import math NEW_LINE mod = 1000000007 ; NEW_LINE MAX = 100005 ; NEW_LINE def minimumProductSubsequence ( arr , n , k ) : NEW_LINE INDENT s = [ ] NEW_LINE dp = [ 0 for i in range ( MAX ) ] ; NEW_LINE p = [ 0.0 for i in range ( MAX ) ] ; NEW_LINE dp [ 0 ] = arr [ 0 ] ; NEW_LINE p [ 0 ] = math . log ( arr [ 0 ] ) ; NEW_LINE s . append ( [ p [ 0 ] , dp [ 0 ] ] ) ; NEW_LINE s . sort ( ) NEW_LINE for i in range ( 1 , k ) : NEW_LINE INDENT l = s [ 0 ] [ 0 ] NEW_LINE min = s [ 0 ] [ 1 ] NEW_LINE p [ i ] = math . log ( arr [ i ] ) + l ; NEW_LINE dp [ i ] = ( arr [ i ] * min ) % mod ; NEW_LINE s . append ( [ p [ i ] , dp [ i ] ] ) ; NEW_LINE s . sort ( ) NEW_LINE DEDENT for i in range ( k , n ) : NEW_LINE INDENT l = s [ 0 ] [ 0 ] NEW_LINE min = s [ 0 ] [ 1 ] NEW_LINE p [ i ] = math . log ( arr [ i ] ) + l ; NEW_LINE dp [ i ] = ( arr [ i ] * min ) % mod ; NEW_LINE if [ p [ i - k ] , dp [ i - k ] ] in s : NEW_LINE INDENT s . pop ( s . index ( [ p [ i - k ] , dp [ i - k ] ] ) ) NEW_LINE DEDENT s . append ( [ p [ i ] , dp [ i ] ] ) ; NEW_LINE s . sort ( ) NEW_LINE DEDENT return dp [ n - 1 ] ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 ; NEW_LINE print ( minimumProductSubsequence ( arr , n , k ) ) NEW_LINE DEDENT