Maximize sum of pairwise products generated from the given Arrays | Python3 program for the above approach ; Variables which represent the size of the array ; Stores the results ; Function to return the maximum possible sum ; Stores the count of arrays processed ; If more than two arrays have been processed ; If an already computed subproblem occurred ; Explore all the possible pairs ; Recursive function call ; Memoize the maximum ; Returning the value ; Function to return the maximum sum of products of pairs possible ; Initialising the dp array to - 1 ; Sort the arrays in descending order ; Driver Code
maxN = 201 ; NEW_LINE n1 , n2 , n3 = 0 , 0 , 0 ; NEW_LINE dp = [ [ [ 0 for i in range ( maxN ) ] for j in range ( maxN ) ] for j in range ( maxN ) ] ; NEW_LINE def getMaxSum ( i , j , k , arr1 , arr2 , arr3 ) : NEW_LINE INDENT cnt = 0 ; NEW_LINE if ( i >= n1 ) : NEW_LINE INDENT cnt += 1 ; NEW_LINE DEDENT if ( j >= n2 ) : NEW_LINE INDENT cnt += 1 ; NEW_LINE DEDENT if ( k >= n3 ) : NEW_LINE INDENT cnt += 1 ; NEW_LINE DEDENT if ( cnt >= 2 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ i ] [ j ] [ k ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] [ k ] ; NEW_LINE DEDENT ans = 0 ; NEW_LINE if ( i < n1 and j < n2 ) : NEW_LINE INDENT ans = max ( ans , getMaxSum ( i + 1 , j + 1 , k , arr1 , arr2 , arr3 ) + arr1 [ i ] * arr2 [ j ] ) ; NEW_LINE DEDENT if ( i < n1 and k < n3 ) : NEW_LINE INDENT ans = max ( ans , getMaxSum ( i + 1 , j , k + 1 , arr1 , arr2 , arr3 ) + arr1 [ i ] * arr3 [ k ] ) ; NEW_LINE DEDENT if ( j < n2 and k < n3 ) : NEW_LINE INDENT ans = max ( ans , getMaxSum ( i , j + 1 , k + 1 , arr1 , arr2 , arr3 ) + arr2 [ j ] * arr3 [ k ] ) ; NEW_LINE DEDENT dp [ i ] [ j ] [ k ] = ans ; NEW_LINE return dp [ i ] [ j ] [ k ] ; NEW_LINE DEDENT def reverse ( tmp ) : NEW_LINE INDENT i , k , t = 0 , 0 , 0 ; NEW_LINE n = len ( tmp ) ; NEW_LINE for i in range ( n // 2 ) : NEW_LINE INDENT t = tmp [ i ] ; NEW_LINE tmp [ i ] = tmp [ n - i - 1 ] ; NEW_LINE tmp [ n - i - 1 ] = t ; NEW_LINE DEDENT DEDENT def maxProductSum ( arr1 , arr2 , arr3 ) : NEW_LINE INDENT for i in range ( len ( dp ) ) : NEW_LINE INDENT for j in range ( len ( dp [ 0 ] ) ) : NEW_LINE INDENT for k in range ( len ( dp [ j ] [ 0 ] ) ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = - 1 ; NEW_LINE DEDENT DEDENT DEDENT arr1 . sort ( ) ; NEW_LINE reverse ( arr1 ) ; NEW_LINE arr2 . sort ( ) ; NEW_LINE reverse ( arr2 ) ; NEW_LINE arr3 . sort ( ) ; NEW_LINE reverse ( arr3 ) ; NEW_LINE return getMaxSum ( 0 , 0 , 0 , arr1 , arr2 , arr3 ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n1 = 2 ; NEW_LINE arr1 = [ 3 , 5 ] ; NEW_LINE n2 = 2 ; NEW_LINE arr2 = [ 2 , 1 ] ; NEW_LINE n3 = 3 ; NEW_LINE arr3 = [ 4 , 3 , 5 ] ; NEW_LINE print ( maxProductSum ( arr1 , arr2 , arr3 ) ) ; NEW_LINE DEDENT