text: Maximize sum of pairwise products generated from the given Arrays | C ++ Program to implement 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define maxN  201 NEW_LINE int n1 , n2 , n3 ; int dp [ maxN ] [ maxN ] [ maxN ] ; int getMaxSum ( int i , int j , int k , int arr1 [ ] , int arr2 [ ] , int arr3 [ ] ) { int cnt = 0 ; if ( i >= n1 ) cnt ++ ; if ( j >= n2 ) cnt ++ ; if ( k >= n3 ) cnt ++ ; if ( cnt >= 2 ) return 0 ; if ( dp [ i ] [ j ] [ k ] != -1 ) return dp [ i ] [ j ] [ k ] ; int ans = 0 ; if ( i < n1 && j < n2 ) ans = max ( ans , getMaxSum ( i + 1 , j + 1 , k , arr1 , arr2 , arr3 ) + arr1 [ i ] * arr2 [ j ] ) ; if ( i < n1 && k < n3 ) ans = max ( ans , getMaxSum ( i + 1 , j , k + 1 , arr1 , arr2 , arr3 ) + arr1 [ i ] * arr3 [ k ] ) ; if ( j < n2 && k < n3 ) ans = max ( ans , getMaxSum ( i , j + 1 , k + 1 , arr1 , arr2 , arr3 ) + arr2 [ j ] * arr3 [ k ] ) ; dp [ i ] [ j ] [ k ] = ans ; return dp [ i ] [ j ] [ k ] ; } int maxProductSum ( int arr1 [ ] , int arr2 [ ] , int arr3 [ ] ) { memset ( dp , -1 , sizeof ( dp ) ) ; sort ( arr1 , arr1 + n1 ) ; reverse ( arr1 , arr1 + n1 ) ; sort ( arr2 , arr2 + n2 ) ; reverse ( arr2 , arr2 + n2 ) ; sort ( arr3 , arr3 + n3 ) ; reverse ( arr3 , arr3 + n3 ) ; return getMaxSum ( 0 , 0 , 0 , arr1 , arr2 , arr3 ) ; } int main ( ) { n1 = 2 ; int arr1 [ ] = { 3 , 5 } ; n2 = 2 ; int arr2 [ ] = { 2 , 1 } ; n3 = 3 ; int arr3 [ ] = { 4 , 3 , 5 } ; cout << maxProductSum ( arr1 , arr2 , arr3 ) ; return 0 ; }