Max Dot Product of Two Subsequences

• Define a recursive function, let's call it solve(i, j), which computes the maximum dot product for the prefixes nums1[0...i] and nums2[0...j].
• Use a 2D array, memo, of the same dimensions as the problem space (m x n) to store the results of subproblems. Initialize it with a sentinel value (e.g., Integer.MIN_VALUE) to mark states as uncomputed.
• In the solve(i, j) function, first check if memo[i][j] already has a computed value. If so, return it immediately.
• If the state is uncomputed, calculate the result based on three possibilities:
  1. Take both nums1[i] and nums2[j]: The value is nums1[i] * nums2[j]. This can be added to the best result from solve(i-1, j-1) if that result is positive. So, this path yields nums1[i] * nums2[j] + max(0, solve(i-1, j-1)).
  2. Skip nums1[i]: The result is determined by the subproblem solve(i-1, j).
  3. Skip nums2[j]: The result is determined by the subproblem solve(i, j-1).
• The value for solve(i, j) is the maximum of these three possibilities.
• Store the computed result in memo[i][j] before returning it.
• The base cases for the recursion are when i or j go below 0, for which we should return a very small number to ensure these paths aren't chosen unless necessary.
• The final answer is obtained by calling solve(m-1, n-1).

The core of this method is a recursive function, say solve(i, j), that calculates the maximum dot product considering nums1 up to index i and nums2 up to index j. The state transition is determined by considering the elements nums1[i] and nums2[j]. We have three choices:

1. We pair nums1[i] with nums2[j]. The product is nums1[i] * nums2[j]. We can either start a new subsequence of length one with this pair or append it to an existing optimal subsequence from nums1[0...i-1] and nums2[0...j-1]. We choose whichever is better, which is captured by nums1[i] * nums2[j] + max(0, solve(i-1, j-1)). The max(0, ...) part cleverly handles the decision of whether to extend a previous subsequence or start anew.
2. We don't use nums1[i]. The maximum dot product is then found in the subproblem solve(i-1, j).
3. We don't use nums2[j]. The maximum dot product is then found in the subproblem solve(i, j-1).

The result for solve(i, j) is the maximum of these three outcomes. A 2D array memo is used to cache the results, preventing exponential complexity.

1class Solution {2    private int[][] memo;3    private int[] nums1;4    private int[] nums2;5 6    public int maxDotProduct(int[] nums1, int[] nums2) {7        this.nums1 = nums1;8        this.nums2 = nums2;9        this.memo = new int[nums1.length][nums2.length];10        for (int i = 0; i < nums1.length; i++) {11            java.util.Arrays.fill(memo[i], Integer.MIN_VALUE);12        }13        return solve(nums1.length - 1, nums2.length - 1);14    }15 16    private int solve(int i, int j) {17        if (i < 0 || j < 0) {18            // Return a very small value that won't be chosen as a max19            // unless it's part of a sum that becomes positive.20            return -1_000_000_000;21        }22        if (memo[i][j] != Integer.MIN_VALUE) {23            return memo[i][j];24        }25 26        int product = nums1[i] * nums2[j];27 28        // Option 1: Take nums1[i] and nums2[j].29        // It can be a new subsequence or appended to a previous one.30        int take_both = product + Math.max(0, solve(i - 1, j - 1));31 32        // Option 2: Skip nums1[i] (result from subproblem on nums1's prefix).33        int skip_i = solve(i - 1, j);34 35        // Option 3: Skip nums2[j] (result from subproblem on nums2's prefix).36        int skip_j = solve(i, j - 1);37        38        // The result is the maximum of all possibilities.39        memo[i][j] = Math.max(take_both, Math.max(skip_i, skip_j));40        return memo[i][j];41    }42}

• Create a 2D array dp of size m x n, where dp[i][j] will store the maximum dot product for prefixes nums1[0...i] and nums2[0...j].
• Iterate through the dp table row by row (i from 0 to m-1) and column by column (j from 0 to n-1).
• For each cell dp[i][j], calculate the value using the same logic as the recursive approach, but using values already computed in the dp table.
• The value dp[i][j] is the maximum of:
  1. nums1[i] * nums2[j] + max(0, dp[i-1][j-1]) (if i>0, j>0). For the edges (i=0 or j=0), this is just nums1[i] * nums2[j].
  2. dp[i-1][j] (if i>0).
  3. dp[i][j-1] (if j>0).
• Carefully handle the boundary conditions where i=0 or j=0.
• After filling the entire table, the value at dp[m-1][n-1] will be the final answer.

We initialize a 2D array dp of size m x n. We then use nested loops to fill this table. The outer loop runs from i = 0 to m-1 and the inner loop from j = 0 to n-1. For each cell dp[i][j], we compute its value based on the values in previously filled cells, specifically dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. The transition logic remains the same as in the memoized approach.

• dp[i][j] is the max of:
  • Taking nums1[i] and nums2[j]: nums1[i] * nums2[j] + (i>0 && j>0 ? Math.max(0, dp[i-1][j-1]) : 0)
  • Skipping nums1[i]: dp[i-1][j] (if i>0)
  • Skipping nums2[j]: dp[i][j-1] (if j>0)

This method avoids recursion overhead and is generally slightly faster in practice than the top-down approach.

1class Solution {2    public int maxDotProduct(int[] nums1, int[] nums2) {3        int m = nums1.length;4        int n = nums2.length;5        int[][] dp = new int[m][n];6 7        for (int i = 0; i < m; i++) {8            for (int j = 0; j < n; j++) {9                int product = nums1[i] * nums2[j];10                11                // Base case for take_both: just the product itself.12                int take_both = product;13                // If possible, add the best previous result.14                if (i > 0 && j > 0) {15                    take_both += Math.max(0, dp[i - 1][j - 1]);16                }17                18                dp[i][j] = take_both;19 20                // Consider not taking nums1[i]21                if (i > 0) {22                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);23                }24 25                // Consider not taking nums2[j]26                if (j > 0) {27                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);28                }29            }30        }31        return dp[m - 1][n - 1];32    }33}

• Observe that the calculation of dp[i][j] only depends on values from the current row (i) and the previous row (i-1). Specifically, it needs dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].
• This dependency allows us to optimize space. Instead of a full m x n table, we only need two 1D arrays to represent the previous and current rows. Let's call them prev_dp and curr_dp, each of size n (assuming n <= m).
• Iterate i from 0 to m-1. In each iteration, compute the curr_dp array for row i.
• The value curr_dp[j] is calculated using prev_dp[j], curr_dp[j-1], and prev_dp[j-1].
• After the inner loop (for j) completes, the curr_dp array holds all the values for row i. We then update prev_dp to be curr_dp for the next iteration i+1.
• To be truly space-efficient, we should ensure the 1D arrays are sized according to the smaller of the two input arrays.
• The final answer is the last element of the prev_dp array after the outer loop finishes.

We can optimize the space of the bottom-up DP solution. We use two 1D arrays, prev_dp and curr_dp, to store the DP values for the previous and current rows of nums1, respectively. The size of these arrays will be n, the length of nums2. We iterate through nums1 with index i, and for each i, we compute curr_dp based on prev_dp.

The recurrence relation dp[i][j] = max(take_both, dp[i-1][j], dp[i][j-1]) is translated as follows:

• dp[i-1][j] becomes prev_dp[j]
• dp[i][j-1] becomes curr_dp[j-1]
• dp[i-1][j-1] becomes prev_dp[j-1]

After computing the curr_dp for the current i, we set prev_dp = curr_dp to prepare for the next iteration. To minimize space, we can ensure n is the length of the smaller array by swapping the inputs if necessary.

1class Solution {2    public int maxDotProduct(int[] nums1, int[] nums2) {3        int m = nums1.length;4        int n = nums2.length;5 6        // To optimize space, we want the smaller array to determine the DP array size.7        if (m < n) {8            return maxDotProduct(nums2, nums1); // Swap arrays9        }10        // Now, m >= n.11 12        int[] prev_dp = new int[n];13        // Initialize prev_dp for the first row (i=0)14        for (int j = 0; j < n; j++) {15            prev_dp[j] = nums1[0] * nums2[j];16            if (j > 0) {17                prev_dp[j] = Math.max(prev_dp[j], prev_dp[j - 1]);18            }19        }20 21        for (int i = 1; i < m; i++) {22            int[] curr_dp = new int[n];23            for (int j = 0; j < n; j++) {24                int product = nums1[i] * nums2[j];25                26                int take_both = product;27                if (j > 0) {28                    take_both += Math.max(0, prev_dp[j - 1]);29                }30                31                curr_dp[j] = take_both;32                33                // Max with skipping nums1[i] (value from previous row, same column)34                curr_dp[j] = Math.max(curr_dp[j], prev_dp[j]);35                36                // Max with skipping nums2[j] (value from current row, previous column)37                if (j > 0) {38                    curr_dp[j] = Math.max(curr_dp[j], curr_dp[j - 1]);39                }40            }41            prev_dp = curr_dp; // Current row becomes previous for the next iteration42        }43 44        return prev_dp[n - 1];45    }46}

Note: The provided code snippet has a slightly more optimized initialization for clarity and correctness, handling the first row separately before the main loop.