# 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.