Maximize product of digit sum of consecutive pairs in a subsequence of length K | Java 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 java . util . * ; class GFG { static int MAX = 100 ; static int dp [ ] [ ] [ ] = new int [ 1000 ] [ MAX ] [ MAX ] ; static int productDigitSum ( int x , int y ) { int sumx = 0 ; while ( x > 0 ) { sumx += ( x % 10 ) ; x /= 10 ; } int sumy = 0 ; while ( y > 0 ) { sumy += ( y % 10 ) ; y /= 10 ; } return ( sumx * sumy ) ; } static int solve ( int arr [ ] , int i , int len , int prev , int n , int k ) { if ( len == k ) return 0 ; if ( i == n ) return Integer . MIN_VALUE ; if ( dp [ i ] [ len ] [ prev ] != 0 ) return dp [ i ] [ len ] [ prev ] ; int inc = 0 , exc = 0 ; if ( ( len & 1 ) != 0 ) { inc = ( productDigitSum ( arr [ prev ] , arr [ i ] ) + solve ( arr , i + 1 , len + 1 , 0 , n , k ) ) ; } else { inc = solve ( arr , i + 1 , len + 1 , i , n , k ) ; } exc = solve ( arr , i + 1 , len , prev , n , k ) ; return dp [ i ] [ len ] [ prev ] = Math . max ( inc , exc ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 10 , 5 , 9 , 101 , 24 , 2 , 20 , 14 } ; int n = arr . length ; int k = 6 ; System . out . print ( solve ( arr , 0 , 0 , 0 , n , k ) ) ; } }