Given three arrays arr1[], arr2[] and arr3[] of length N1, N2, and N3 respectively, the task is to find the maximum sum possible by adding the products of pairs taken from different arrays.
Note: Each array element can be a part of a single pair.
Examples:
Input: arr1[] = {3, 5}, arr2[] = {2, 1}, arr3[] = {4, 3, 5}
Output : 43
Explanation
After sorting the arrays in descending order, following modifications are obtained: arr1[] = {5, 3}, arr2[] = {2, 1}, arr3[] = {5, 4, 3}.
Therefore, maximized product = (arr1[0] * arr3[0]) + (arr1[1] * arr3[1]) + (arr2[0] * arr3[2]) = (5*5 + 3*4 + 2*3) = 43Input: arr1[] = {3, 5, 9, 8, 7}, arr2[] = {6}, arr3[] = {3, 5}
Output : 115
Explanation
Sort the arrays in descending order, the following modifications are obtained: arr1[] = {9, 8, 7, 5, 3}, arr2[] = {6}, arr3[] = {5, 3}.
Therefore, maximized product = (arr1[0] * arr2[0]) + (arr1[1] * arr3[0]) + (arr1[2] * arr3[1]) = (9*6 + 8*5 + 7*3) = 155
Approach: The given problem can be solved using a 3D Memoization table to store the maximum sums for all possible combinations of pairs. Suppose i, j, k are the number of elements taken from the arrays arr1[], arr2[] and arr3[] respectively to form pairs, then the memorization table dp[][][] will store the maximum possible sum of products generated from this combination of elements in dp[i][j][k].
Follow the below steps to solve the problem-
- Sort the given arrays in descending order.
- Initialize a dp table dp[][][], where dp[i][j][k] store the maximum sum obtained by taking i largest numbers from the first array, j largest numbers from the second array, and k largest numbers from the third array.
- For every i, j, and kth element from the three arrays respectively, check for all possible pairs and calculate the maximum sum possible by considering each pair and memoize the maximum sum obtained for further computation.
- Finally, print the maximum possible sum returned by the dp[][][] matrix.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define maxN 201// Variables which represent// the size of the arrayint n1, n2, n3;// Stores the resultsint dp[maxN][maxN][maxN];// Function to return the// maximum possible sumint getMaxSum(int i, int j, int k, int arr1[], int arr2[], int arr3[]){ // Stores the count of // arrays processed int cnt = 0; if (i >= n1) cnt++; if (j >= n2) cnt++; if (k >= n3) cnt++; // If more than two arrays // have been processed if (cnt >= 2) return 0; // If an already computed // subproblem occurred if (dp[i][j][k] != -1) return dp[i][j][k]; int ans = 0; // Explore all the possible pairs if (i < n1 && j < n2) // Recursive function call 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]); // Memoize the maximum dp[i][j][k] = ans; // Returning the value return dp[i][j][k];}// Function to return the maximum sum of// products of pairs possibleint maxProductSum(int arr1[], int arr2[], int arr3[]){ // Initialising the dp array to -1 memset(dp, -1, sizeof(dp)); // Sort the arrays in descending order 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);}// Driver Codeint 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;} |
Java
// Java program for above approachimport java.util.*;import java.lang.*;class GFG{static final int maxN = 201; // Variables which represent // the size of the array static int n1, n2, n3; // Stores the results static int[][][] dp = new int[maxN][maxN][maxN]; // Function to return the // maximum possible sum static int getMaxSum(int i, int j, int k, int arr1[], int arr2[], int arr3[]) { // Stores the count of // arrays processed int cnt = 0; if (i >= n1) cnt++; if (j >= n2) cnt++; if (k >= n3) cnt++; // If more than two arrays // have been processed if (cnt >= 2) return 0; // If an already computed // subproblem occurred if (dp[i][j][k] != -1) return dp[i][j][k]; int ans = 0; // Explore all the possible pairs if (i < n1 && j < n2) // Recursive function call 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]); // Memoize the maximum dp[i][j][k] = ans; // Returning the value 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; } }// Function to return the maximum sum of // products of pairs possible static int maxProductSum(int arr1[], int arr2[], int arr3[]) { // Initialising the dp array to -1 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; // Sort the arrays in descending order Arrays.sort(arr1); reverse(arr1); Arrays.sort(arr2); reverse(arr2); Arrays.sort(arr3); reverse(arr3); return getMaxSum(0, 0, 0, arr1, arr2, arr3); } // Driver Codepublic 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)); }}// This code is contributed by offbeat |
Python3
# Python3 program for # the above approachmaxN = 201;# Variables which represent# the size of the arrayn1, n2, n3 = 0, 0, 0;# Stores the resultsdp = [[[0 for i in range(maxN)] for j in range(maxN)] for j in range(maxN)];# Function to return the# maximum possible sumdef getMaxSum(i, j, k, arr1, arr2, arr3): # Stores the count of # arrays processed cnt = 0; if (i >= n1): cnt += 1; if (j >= n2): cnt += 1; if (k >= n3): cnt += 1; # If more than two arrays # have been processed if (cnt >= 2): return 0; # If an already computed # subproblem occurred if (dp[i][j][k] != -1): return dp[i][j][k]; ans = 0; # Explore all the possible pairs if (i < n1 and j < n2): # Recursive function call ans = max(ans, getMaxSum(i + 1, j + 1, k, arr1, arr2, arr3) + arr1[i] * arr2[j]); if (i < n1 and k < n3): ans = max(ans, getMaxSum(i + 1, j, k + 1, arr1, arr2, arr3) + arr1[i] * arr3[k]); if (j < n2 and k < n3): ans = max(ans, getMaxSum(i, j + 1, k + 1, arr1, arr2, arr3) + arr2[j] * arr3[k]); # Memoize the maximum dp[i][j][k] = ans; # Returning the value return dp[i][j][k];def reverse(tmp): i, k, t = 0, 0, 0; n = len(tmp); for i in range(n // 2): t = tmp[i]; tmp[i] = tmp[n - i - 1]; tmp[n - i - 1] = t;# Function to return the maximum sum of# products of pairs possibledef maxProductSum(arr1, arr2, arr3): # Initialising the dp array to -1 for i in range(len(dp)): for j in range(len(dp[0])): for k in range(len(dp[j][0])): dp[i][j][k] = -1; # Sort the arrays in descending order arr1.sort(); reverse(arr1); arr2.sort(); reverse(arr2); arr3.sort(); reverse(arr3); return getMaxSum(0, 0, 0, arr1, arr2, arr3);# Driver Codeif __name__ == '__main__': n1 = 2; arr1 = [3, 5]; n2 = 2; arr2 = [2, 1]; n3 = 3; arr3 = [4, 3, 5]; print(maxProductSum(arr1, arr2, arr3));# This code is contributed by Rajput-Ji |
C#
// C# program for above approach using System; class GFG{ const int maxN = 201; // Variables which represent // the size of the array static int n1, n2, n3; // Stores the results static int[,,] dp = new int[maxN, maxN, maxN]; // Function to return the // maximum possible sum static int getMaxSum(int i, int j, int k, int []arr1, int []arr2, int []arr3) { // Stores the count of // arrays processed int cnt = 0; if (i >= n1) cnt++; if (j >= n2) cnt++; if (k >= n3) cnt++; // If more than two arrays // have been processed if (cnt >= 2) return 0; // If an already computed // subproblem occurred if (dp[i, j, k] != -1) return dp[i, j, k]; int ans = 0; // Explore all the possible pairs if (i < n1 && j < n2) // Recursive function call 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]); // Memoize the maximum dp[i, j, k] = ans; // Returning the value return dp[i, j, k]; } static void reverse(int[] tmp) { int i, 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; } } // Function to return the maximum sum of // products of pairs possible static int maxProductSum(int []arr1, int []arr2, int []arr3) { // Initialising the dp array to -1 for(int i = 0; i < maxN; i++) for(int j = 0; j < maxN; j++) for(int k = 0; k < maxN; k++) dp[i, j, k] = -1; // Sort the arrays in descending order Array.Sort(arr1); reverse(arr1); Array.Sort(arr2); reverse(arr2); Array.Sort(arr3); reverse(arr3); return getMaxSum(0, 0, 0, arr1, arr2, arr3); } // Driver Code 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 }; Console.Write(maxProductSum(arr1, arr2, arr3)); } } // This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript Program to implement// the above approachvar maxN = 201;// Variables which represent// the size of the arrayvar n1, n2, n3;// Stores the resultsvar dp = Array.from(Array(maxN), ()=>Array(maxN));for(var i =0; i<maxN; i++) for(var j =0; j<maxN; j++) dp[i][j] = new Array(maxN).fill(-1);// Function to return the// maximum possible sumfunction getMaxSum(i, j, k, arr1, arr2, arr3){ // Stores the count of // arrays processed var cnt = 0; if (i >= n1) cnt++; if (j >= n2) cnt++; if (k >= n3) cnt++; // If more than two arrays // have been processed if (cnt >= 2) return 0; // If an already computed // subproblem occurred if (dp[i][j][k] != -1) return dp[i][j][k]; var ans = 0; // Explore all the possible pairs if (i < n1 && j < n2) // Recursive function call 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]); // Memoize the maximum dp[i][j][k] = ans; // Returning the value return dp[i][j][k];}// Function to return the maximum sum of// products of pairs possiblefunction maxProductSum(arr1, arr2, arr3){ // Sort the arrays in descending order arr1.sort(); arr1.reverse(); arr2.sort(); arr2.reverse(); arr3.sort(); arr3.reverse(); return getMaxSum(0, 0, 0, arr1, arr2, arr3);}// Driver Coden1 = 2;var arr1 = [3, 5];n2 = 2;var arr2 = [2, 1];n3 = 3;var arr3 = [4, 3, 5];document.write( maxProductSum(arr1, arr2, arr3));</script> |
Output:
43
Time Complexity: O((N1 * N2 * N3))
Auxiliary Space: O(N1 * N2 * N3)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
