Maximize dot product problem in Java
Given arrays a and b, maximize the dot product by pairwise multiplication of elements from arrays a and b. It is accomplished by aligning the elements of b with those of a and adding zeros in b as needed to maintain alignment.
Example:
Input: a: {2, 4, 6}
b: {3}
Output: Maximum Dot Product: 18
Explanation: Aligning array b with array a by inserting zeros yields {0, 0, 3}. The maximum dot product is obtained as follows:
2*0 + 4*0 + 6*3 = 18
Recursive Approach
Algorithm
Step 1: Take arrays a and b, and indices i and j as parameters.
Step 2: Return the maximum dot product considering elements up to indices i and j.
Step 3: If i or j is less than 0, return 0.
Step 4: Compute ans1 by multiplying elements at i and j and add it to the result of the recursive call with i-1 and j-1.
Step 5: Calculate ans2 as 0 if i is greater than j, else recursively call with i-1 and j.
Step 6: Start recursion with last indices of arrays a and b.
FileName: MaxDotProductRecursive.java
public class MaxDotProductRecursive { // Function to solve the maximum dot product recursively public static int solveRec(int[] a, int[] b, int i, int j) { if (i < 0 || j < 0) return 0; int ans1 = a[i] * b[j] + solveRec(a, b, i - 1, j - 1); int ans2 = 0; if (i > j) ans2 = 0 + solveRec(a, b, i - 1, j); return Math.max(ans1, ans2); } // Wrapper function to start the recursive calculation public static int calculateDotProduct(int[] a, int[] b) { return solveRec(a, b, a.length - 1, b.length - 1); } public static void main(String[] args) { int[] a = {2, 4, 6}; int[] b = {3}; // Calculate and print the maximum dot product System.out.println("Maximum Dot Product: " + calculateDotProduct(a, b)); } }
Output:
Maximum Dot Product: 18
Complexity Analysis: The time complexity of the code is O(2^n), where n is the size of the larger array among a and b and space complexity is O(n).
Space Optimized Dynamic Programming Approach
Algorithm
Step 1: Initialize an array to store the previous row of values.
Step 2: Initialize the previous row with zeros.
Step 3: Iterate through each element in array a.
Step 4: Iterate from the end of array b to the beginning.
Step 5: Calculate the dot product with the current elements of a and b, adding it to the dot product calculated in the previous row.
Step 6: If a has more elements than b, consider inserting zeros.
Step 7: Update the current value in the prev array with the maximum of calculated dot products.
Step 8: Return the maximum dot product calculated.
FileName: MaxDotProductSpaceOptimized.java
public class MaxDotProductSpaceOptimized { // Function to solve the maximum dot product using space-optimized DP public static int solveSpaceOpti2(int[] a, int[] b, int n, int m) { // Initialize an array to store the previous row of values int[] prev = new int[m + 1]; // Initialize the previous row with zeros for (int j = 0; j <= m; j++) prev[j] = 0; // Iterate through each element in array 'a' for (int i = 1; i <= n; i++) { // Iterate from the end of array 'b' to the beginning for (int j = m; j >= 1; j--) { // Calculate the dot product with the current elements of 'a' and 'b', // and add it to the dot product calculated in the previous row int ans1 = a[i - 1] * b[j - 1] + prev[j - 1]; // If 'a' has more elements than 'b', consider inserting zeros int ans2 = 0; if (i > j) ans2 = 0 + prev[j]; // Update the current value in the 'prev' array with the maximum of ans1 and ans2 prev[j] = Math.max(ans1, ans2); } } // Return the maximum dot product calculated return prev[m]; } public static void main(String[] args) { int[] a = {2, 4, 6}; int[] b = {3}; int n = a.length; int m = b.length; // Calculate and print the maximum dot product System.out.println("Maximum Dot Product: " + solveSpaceOpti2(a, b, n, m)); } }
Output:
Maximum Dot Product: 18
Complexity Analysis: The time complexity of the code is O(n * m), where n and m are the lengths of arrays a and b respectively. The space complexity is O(m), where m is the length of array b, due to the usage of the prev array.
Dynamic Programming Approach
Algorithm
Step 1: Create a 2D array dp with dimensions (n+1) * (m+1) to store maximum dot products.
Step 2: Iterate through a and b elements using nested loops.
Step 3: Update dp cells based on the maximum dot product of subproblems.
Step 4: Calculate dot product for each pair of elements from a and b.
Step 5: Update dp cells with the maximum dot product considering current elements.
Step 6: After filling dp, retrieve the maximum dot product from dp[n][m].
FileName: MaxDotProductDynamicProgramming.java
public class MaxDotProductDynamicProgramming { // Function to calculate the dot product of two arrays public static int calculateDotProduct(int[] a, int[] b) { int n = a.length; int m = b.length; // Create a 2D array to store the maximum dot product for subproblems int[][] dp = new int[n + 1][m + 1]; // Fill the dp array using dynamic programming for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1] * b[j - 1]); } } return dp[n][m]; } public static void main(String[] args) { int[] a = {2, 4, 6}; int[] b = {3}; // Calculate and print the maximum dot product System.out.println("Maximum Dot Product: " + calculateDotProduct(a, b)); } }
Output:
Maximum Dot Product: 18
Complexity Analysis: The time complexity for the code is O(n * m), where n and m are the lengths of arrays a and b respectively, and the space complexity is also O(n * m) as it requires a 2D array dp to store the maximum dot product for subproblems, consuming additional space proportional to the product of n and m.