Maximize product of digit sum of consecutive pairs in a subsequence of length K | Python3 implementation to find the maximum product of the digit sum of the consecutive pairs of the subsequence of the length K ; Function to find the product of two numbers digit sum in the pair ; Loop to find the digits of the number ; Loop to find the digits of other number ; Function to find the subsequence of the length K ; Base case ; Condition when we didn 't reach  the length K, but ran out of  elements of the array ; Condition if already calculated ; If length upto this point is odd ; If length is odd , it means we need second element of this current pair , calculate the product of digit sum of current and previous element and recur by moving towards next index ; If length upto this point is even ; Exclude this current element and recur for next elements . ; Return by memoizing it , by selecting the maximum among two choices . ; Driver code
import sys NEW_LINE MAX = 100 NEW_LINE dp = [ ] NEW_LINE for i in range ( 1000 ) : NEW_LINE INDENT temp1 = [ ] NEW_LINE for j in range ( MAX ) : NEW_LINE INDENT temp2 = [ ] NEW_LINE for k in range ( MAX ) : NEW_LINE INDENT temp2 . append ( 0 ) NEW_LINE DEDENT temp1 . append ( temp2 ) NEW_LINE DEDENT dp . append ( temp1 ) NEW_LINE DEDENT def productDigitSum ( x , y ) : NEW_LINE INDENT sumx = 0 NEW_LINE while x : NEW_LINE INDENT sumx += x % 10 NEW_LINE x = x // 10 NEW_LINE DEDENT sumy = 0 NEW_LINE while y : NEW_LINE INDENT sumy += y % 10 NEW_LINE y = y // 10 NEW_LINE DEDENT return sumx * sumy NEW_LINE DEDENT def solve ( arr , i , len , prev , n , k ) : NEW_LINE INDENT if len == k : NEW_LINE INDENT return 0 NEW_LINE DEDENT if i == n : NEW_LINE INDENT return - sys . maxsize - 1 NEW_LINE DEDENT if dp [ i ] [ len ] [ prev ] : NEW_LINE INDENT return dp [ i ] [ len ] [ prev ] NEW_LINE DEDENT if len & 1 : NEW_LINE INDENT inc = ( productDigitSum ( arr [ prev ] , arr [ i ] ) + solve ( arr , i + 1 , len + 1 , i , n , k ) ) NEW_LINE DEDENT else : NEW_LINE INDENT inc = solve ( arr , i + 1 , len + 1 , i , n , k ) NEW_LINE DEDENT exc = solve ( arr , i + 1 , len , prev , n , k ) NEW_LINE dp [ i ] [ len ] [ prev ] = max ( inc , exc ) NEW_LINE return dp [ i ] [ len ] [ prev ] NEW_LINE DEDENT arr = [ 10 , 5 , 9 , 101 , 24 , 2 , 20 , 14 ] NEW_LINE n = len ( arr ) NEW_LINE k = 6 NEW_LINE print ( solve ( arr , 0 , 0 , 0 , n , k ) ) NEW_LINE