Given two arrays of positive integers of size m and n where m > n. We need to maximize the dot product by inserting zeros in the second array but we cannot disturb the order of elements.
Examples:
Input : A[] = {2, 3 , 1, 7, 8} , B[] = {3, 6, 7}
Output : 107
Explanation : We get maximum dot product after inserting 0 at first and third positions in second array.
Maximum Dot Product : = A[i] * B[j]
2*0 + 3*3 + 1*0 + 7*6 + 8*7 = 107Input : A[] = {1, 2, 3, 6, 1, 4}, B[] = {4, 5, 1}
Output : 46
Asked in: Directi Interview
Another way to look at this problem is, for every pair of elements element A[i] and B[j] where j >= i , we have two choices:
- We multiply A[i] and B[j] and add to the product (We include A[i]).
- We exclude A[i] from the product (In other words, we insert 0 at the current position in B[])
The idea is to use Dynamic programming .
1) Given Array A[] of size 'm' and B[] of size 'n'
2) Create 2D matrix 'DP[n + 1][m + 1]' initialize it
with '0'
3) Run loop outer loop for i = 1 to n
Inner loop j = i to m
// Two cases arise
// 1) Include A[j]
// 2) Exclude A[j] (insert 0 in B[])
dp[i][j] = max(dp[i-1][j-1] + A[j-1] * B[i -1],
dp[i][j-1])
// Last return maximum dot product that is
return dp[n][m]
Below is the implementation of the above idea.
C++
// C++ program to find maximum dot product of two array#include<bits/stdc++.h>using namespace std;// Function compute Maximum Dot Product and// return itlong long int MaxDotProduct(int A[], int B[], int m, int n){ // Create 2D Matrix that stores dot product // dp[i+1][j+1] stores product considering B[0..i] // and A[0...j]. Note that since all m > n, we fill // values in upper diagonal of dp[][] long long int dp[n+1][m+1]; memset(dp, 0, sizeof(dp)); // Traverse through all elements of B[] for (int i=1; i<=n; i++) // Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for (int j=i; j<=m; j++) // Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = max((dp[i-1][j-1] + (A[j-1]*B[i-1])) , dp[i][j-1]); // return Maximum Dot Product return dp[n][m] ;}// Driver program to test above functionint main(){ int A[] = { 2, 3 , 1, 7, 8 } ; int B[] = { 3, 6, 7 } ; int m = sizeof(A)/sizeof(A[0]); int n = sizeof(B)/sizeof(B[0]); cout << MaxDotProduct(A, B, m, n); return 0;} |
Java
// Java program to find maximum // dot product of two arrayimport java.util.*;class GFG {// Function to compute Maximum // Dot Product and return itstatic int MaxDotProduct(int A[], int B[], int m, int n){ // Create 2D Matrix that stores dot product // dp[i+1][j+1] stores product considering B[0..i] // and A[0...j]. Note that since all m > n, we fill // values in upper diagonal of dp[][] int dp[][] = new int[n + 1][m + 1]; for (int[] row : dp) Arrays.fill(row, 0); // Traverse through all elements of B[] for (int i = 1; i <= n; i++) // Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for (int j = i; j <= m; j++) // Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = Math.max((dp[i - 1][j - 1] + (A[j - 1] * B[i - 1])), dp[i][j - 1]); // return Maximum Dot Product return dp[n][m];}// Driver codepublic static void main(String[] args) { int A[] = {2, 3, 1, 7, 8}; int B[] = {3, 6, 7}; int m = A.length; int n = B.length; System.out.print(MaxDotProduct(A, B, m, n));}}// This code is contributed by Anant Agarwal. |
Python3
# Python 3 program to find maximum dot# product of two array# Function compute Maximum Dot Product # and return itdef MaxDotProduct(A, B, m, n): # Create 2D Matrix that stores dot product # dp[i+1][j+1] stores product considering # B[0..i] and A[0...j]. Note that since # all m > n, we fill values in upper # diagonal of dp[][] dp = [[0 for i in range(m + 1)] for j in range(n + 1)] # Traverse through all elements of B[] for i in range(1, n + 1, 1): # Consider all values of A[] with indexes # greater than or equal to i and compute # dp[i][j] for j in range(i, m + 1, 1): # Two cases arise # 1) Include A[j] # 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = max((dp[i - 1][j - 1] + (A[j - 1] * B[i - 1])) , dp[i][j - 1]) # return Maximum Dot Product return dp[n][m] # Driver Codeif __name__ == '__main__': A = [2, 3 , 1, 7, 8] B = [3, 6, 7] m = len(A) n = len(B) print(MaxDotProduct(A, B, m, n))# This code is contributed by# Sanjit_Prasad |
C#
// C# program to find maximum // dot product of two arrayusing System; public class GFG{ // Function to compute Maximum // Dot Product and return it static int MaxDotProduct(int []A, int []B, int m, int n) { // Create 2D Matrix that stores dot product // dp[i+1][j+1] stores product considering B[0..i] // and A[0...j]. Note that since all m > n, we fill // values in upper diagonal of dp[][] int [,]dp = new int[n + 1,m + 1]; // Traverse through all elements of B[] for (int i = 1; i <= n; i++) // Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for (int j = i; j <= m; j++) // Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i,j] = Math.Max((dp[i - 1,j - 1] + (A[j - 1] * B[i - 1])), dp[i,j - 1]); // return Maximum Dot Product return dp[n,m]; } // Driver code public static void Main() { int []A = {2, 3, 1, 7, 8}; int []B = {3, 6, 7}; int m = A.Length; int n = B.Length; Console.Write(MaxDotProduct(A, B, m, n)); }}/*This code is contributed by 29AjayKumar*/ |
Javascript
<script>// Javascript program to find maximum // dot product of two array// Function to compute Maximum // Dot Product and return itfunction MaxDotProduct(A, B, m, n){ // Create 2D Matrix that stores dot product // dp[i+1][j+1] stores product considering B[0..i] // and A[0...j]. Note that since all m > n, we fill // values in upper diagonal of dp[][] let dp = new Array(n + 1); for(let i = 0; i < (n + 1); i++) { dp[i] = new Array(m+1); for(let j = 0; j < m + 1; j++) { dp[i][j] = 0; } } // Traverse through all elements of B[] for (let i = 1; i <= n; i++) // Consider all values of A[] with indexes greater // than or equal to i and compute dp[i][j] for (let j = i; j <= m; j++) // Two cases arise // 1) Include A[j] // 2) Exclude A[j] (insert 0 in B[]) dp[i][j] = Math.max((dp[i - 1][j - 1] + (A[j - 1] * B[i - 1])), dp[i][j - 1]); // return Maximum Dot Product return dp[n][m];}// Driver codelet A = [2, 3, 1, 7, 8];let B = [3, 6, 7];let m = A.length;let n = B.length;document.write(MaxDotProduct(A, B, m, n));// This code is contributed by rag2127</script> |
Output
107
Time Complexity : O(n*m)
Auxiliary Space: O(n*m)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create an array dp to store the maximum dot product values.
- Initialize all elements of dp to 0.
- Iterate over the A array and process each element.
- For each element in A, iterate over the B array in reverse order and process each element.
- Update dp[j] with the maximum value between the current dp[j] and dp[j – 1] + (A[i – 1] * B[j – 1]).
- After the loops, dp[n] will represent the maximum dot product achievable.
- Return dp[n] as the result.
Implementation:
C++
#include<bits/stdc++.h>using namespace std;long long int MaxDotProduct(int A[], int B[], int m, int n){ long long int dp[n + 1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= m; i++) { for (int j = n; j >= 1; j--) { dp[j] = max(dp[j], dp[j - 1] + (A[i - 1] * B[j - 1])); // Calculate the maximum dot product at position j // by choosing between not including B[j-1] and including B[j-1] // Update dp[j] with the maximum value } } return dp[n]; // Return the maximum dot product}int main(){ int A[] = { 2, 3, 1, 7, 8 }; int B[] = { 3, 6, 7 }; int m = sizeof(A) / sizeof(A[0]); int n = sizeof(B) / sizeof(B[0]); cout << MaxDotProduct(A, B, m, n); return 0;} |
Java
import java.util.Arrays;public class GFG { // Function to find the maximum dot product of two // arrays static long MaxDotProduct(int[] A, int[] B, int m, int n) { // Initialize an array to store the maximum dot // products at each position in B long[] dp = new long[n + 1]; Arrays.fill(dp, 0); // Initialize the array with zeros // Iterate through each element in array A for (int i = 1; i <= m; i++) { // Iterate through each position in array B in // reverse order for (int j = n; j >= 1; j--) { // Calculate the maximum dot product at // position j by choosing between not // including B[j-1] (dp[j]) and including // B[j-1] (dp[j - 1] + (A[i - 1] * B[j - // 1])) dp[j] = Math.max( dp[j], dp[j - 1] + (A[i - 1] * B[j - 1])); // dp[j] represents the maximum dot product // of A[0...i] and B[0...j] } } // The final result is stored in dp[n], which // represents the maximum dot product of A and B return dp[n]; } public static void main(String[] args) { int[] A = { 2, 3, 1, 7, 8 }; int[] B = { 3, 6, 7 }; int m = A.length; int n = B.length; // Call the MaxDotProduct function and print the // result System.out.println(MaxDotProduct(A, B, m, n)); }} |
Python3
def MaxDotProduct(A, B, m, n): dp = [0] * (n + 1) for i in range(1, m + 1): for j in range(n, 0, -1): dp[j] = max(dp[j], dp[j - 1] + (A[i - 1] * B[j - 1])) # Calculate the maximum dot product at position j # by choosing between not including B[j-1] and # including B[j-1] # Update dp[j] with the maximum value return dp[n] # Return the maximum dot productA = [2, 3, 1, 7, 8]B = [3, 6, 7]m = len(A)n = len(B)print(MaxDotProduct(A, B, m, n)) |
C#
using System;class GFG { // Function to calculate the maximum dot product between // two arrays A and B static long MaxDotProduct(int[] A, int[] B, int m, int n) { // Create an array to store the maximum dot products long[] dp = new long[n + 1]; // Calculate the maximum dot product for each // position j in array B for (int i = 1; i <= m; i++) { for (int j = n; j >= 1; j--) { // Calculate the maximum dot product at // position j by choosing between not // including B[j-1] and including B[j-1]. // Update dp[j] with the maximum value. dp[j] = Math.Max( dp[j], dp[j - 1] + (A[i - 1] * B[j - 1])); } } return dp[n]; // Return the maximum dot product } static void Main() { int[] A = { 2, 3, 1, 7, 8 }; int[] B = { 3, 6, 7 }; int m = A.Length; int n = B.Length; // Calculate and print the maximum dot product // between arrays A and B Console.WriteLine(MaxDotProduct(A, B, m, n)); }} |
Javascript
function MaxDotProduct(A, B, m, n) { // Create an array to store the maximum dot products const dp = new Array(n + 1).fill(0); for (let i = 1; i <= m; i++) { for (let j = n; j >= 1; j--) { // Calculate the maximum dot product at position j // by choosing between not including B[j-1] and including B[j-1] dp[j] = Math.max(dp[j], dp[j - 1] + (A[i - 1] * B[j - 1])); } } return dp[n]; // Return the maximum dot product}// Driver codeconst A = [2, 3, 1, 7, 8];const B = [3, 6, 7];// Calculate the lengths of arrays A and Bconst m = A.length;const n = B.length;// Call the MaxDotProduct function and output the resultconsole.log(MaxDotProduct(A, B, m, n)); |
Output
107
Time Complexity : O(n*m)
Auxiliary Space: O(n)
This article is contributed by Nishant Singh. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
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!
