Maximize sum of pairwise products generated from the given Arrays | Java program for 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
import java . util . * ; import java . lang . * ; class GFG { static final int maxN = 201 ; static int n1 , n2 , n3 ; static int [ ] [ ] [ ] dp = new int [ maxN ] [ maxN ] [ maxN ] ; static 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 = Math . max ( ans , getMaxSum ( i + 1 , j + 1 , k , arr1 , arr2 , arr3 ) + arr1 [ i ] * arr2 [ j ] ) ; if ( i < n1 && k < n3 ) ans = Math . max ( ans , getMaxSum ( i + 1 , j , k + 1 , arr1 , arr2 , arr3 ) + arr1 [ i ] * arr3 [ k ] ) ; if ( j < n2 && k < n3 ) ans = Math . 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 ] ; } static void reverse ( int [ ] tmp ) { int i , k , t ; int n = tmp . length ; for ( i = 0 ; i < n / 2 ; i ++ ) { t = tmp [ i ] ; tmp [ i ] = tmp [ n - i - 1 ] ; tmp [ n - i - 1 ] = t ; } } static int maxProductSum ( int arr1 [ ] , int arr2 [ ] , int arr3 [ ] ) { for ( int i = 0 ; i < dp . length ; i ++ ) for ( int j = 0 ; j < dp [ 0 ] . length ; j ++ ) for ( int k = 0 ; k < dp [ j ] [ 0 ] . length ; k ++ ) dp [ i ] [ j ] [ k ] = - 1 ; Arrays . sort ( arr1 ) ; reverse ( arr1 ) ; Arrays . sort ( arr2 ) ; reverse ( arr2 ) ; Arrays . sort ( arr3 ) ; reverse ( arr3 ) ; return getMaxSum ( 0 , 0 , 0 , arr1 , arr2 , arr3 ) ; } public static void main ( String [ ] args ) { n1 = 2 ; int arr1 [ ] = { 3 , 5 } ; n2 = 2 ; int arr2 [ ] = { 2 , 1 } ; n3 = 3 ; int arr3 [ ] = { 4 , 3 , 5 } ; System . out . println ( maxProductSum ( arr1 , arr2 , arr3 ) ) ; } }