# Max Dot Product of Two Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/max-dot-product-of-two-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/max-dot-product-of-two-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
Given two arrays `nums1` and `nums2`.

Return the maximum dot product between **non-empty** subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `[2,3,5]` is a subsequence of `[1,2,3,4,5]` while `[1,5,3]` is not).

**Example 1:**

**Input:** nums1 = [2,1,-2,5], nums2 = [3,0,-6]
**Output:** 18
**Explanation:** Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

**Example 2:**

**Input:** nums1 = [3,-2], nums2 = [2,-6,7]
**Output:** 21
**Explanation:** Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

**Example 3:**

**Input:** nums1 = [-1,-1], nums2 = [1,1]
**Output:** -1
**Explanation:** Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

**Constraints:**

* `1 <= nums1.length, nums2.length <= 500`
* `-1000 <= nums1[i], nums2[i] <= 1000`

# Approaches
## Top-Down Dynamic Programming (Memoization)
This approach uses recursion combined with memoization to solve the problem, which is a top-down dynamic programming technique. We define a recursive function that explores all possible subsequence pairings. To avoid recomputing results for the same subproblems (i.e., the same prefixes of `nums1` and `nums2`), we store the results in a 2D `memo` table. When the function is called with indices `(i, j)`, it first checks if the result for this state is already computed. If so, it returns the stored value; otherwise, it computes the result, stores it, and then returns it.
**Time:** O(m * n) - Each of the `m * n` states `(i, j)` is computed exactly once. The computation for each state takes constant time. · **Space:** O(m * n) - This is for the `memo` table used to store the results of the subproblems. There is also an additional O(m + n) space cost for the recursion stack in the worst case.
**Pros:** Drastically more efficient than pure recursion by avoiding redundant computations.; The logic often follows the problem's recursive definition, making it intuitive to write.; Guaranteed to find the optimal solution.
**Cons:** May cause a `StackOverflowError` for very deep recursion, although the given constraints (`m, n <= 500`) make this unlikely.; Slightly higher constant factor overhead compared to the iterative bottom-up approach due to function call stacks.
### Explanation
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.

```java
class Solution {
    private int[][] memo;
    private int[] nums1;
    private int[] nums2;

    public int maxDotProduct(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.memo = new int[nums1.length][nums2.length];
        for (int i = 0; i < nums1.length; i++) {
            java.util.Arrays.fill(memo[i], Integer.MIN_VALUE);
        }
        return solve(nums1.length - 1, nums2.length - 1);
    }

    private int solve(int i, int j) {
        if (i < 0 || j < 0) {
            // Return a very small value that won't be chosen as a max
            // unless it's part of a sum that becomes positive.
            return -1_000_000_000;
        }
        if (memo[i][j] != Integer.MIN_VALUE) {
            return memo[i][j];
        }

        int product = nums1[i] * nums2[j];

        // Option 1: Take nums1[i] and nums2[j].
        // It can be a new subsequence or appended to a previous one.
        int take_both = product + Math.max(0, solve(i - 1, j - 1));

        // Option 2: Skip nums1[i] (result from subproblem on nums1's prefix).
        int skip_i = solve(i - 1, j);

        // Option 3: Skip nums2[j] (result from subproblem on nums2's prefix).
        int skip_j = solve(i, j - 1);
        
        // The result is the maximum of all possibilities.
        memo[i][j] = Math.max(take_both, Math.max(skip_i, skip_j));
        return memo[i][j];
    }
}
```
### Algorithm
- 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)`.

## Bottom-Up Dynamic Programming (Tabulation)
This approach, also known as tabulation, solves the problem iteratively. It builds the solution from the bottom up by filling a 2D DP table. The table, say `dp[m][n]`, stores the solutions to subproblems. `dp[i][j]` holds the maximum dot product for the prefixes `nums1[0...i]` and `nums2[0...j]`. By iterating through the arrays and filling the table, we can compute the solution for the entire problem without using recursion.
**Time:** O(m * n) - Due to the nested loops that iterate through all `m * n` states of the DP table. · **Space:** O(m * n) - To store the 2D DP table.
**Pros:** Avoids recursion, eliminating the risk of stack overflow and reducing function call overhead.; Often easier to debug and reason about the state transitions.; Guaranteed to be efficient and optimal.
**Cons:** Uses O(m * n) space, which might be substantial for larger constraints, although it's acceptable for this problem.
### Explanation
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.

```java
class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int product = nums1[i] * nums2[j];
                
                // Base case for take_both: just the product itself.
                int take_both = product;
                // If possible, add the best previous result.
                if (i > 0 && j > 0) {
                    take_both += Math.max(0, dp[i - 1][j - 1]);
                }
                
                dp[i][j] = take_both;

                // Consider not taking nums1[i]
                if (i > 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }

                // Consider not taking nums2[j]
                if (j > 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
```
### Algorithm
- 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.

## Space-Optimized Bottom-Up DP
This is the most efficient approach, building upon the bottom-up DP method. By analyzing the state dependencies, we can see that computing the values for the current row `i` only requires information from the previous row `i-1`. This means we don't need to store the entire 2D DP table. We can optimize the space complexity from O(m*n) down to O(min(m, n)) by only keeping track of the previous and current rows.
**Time:** O(m * n) - The time complexity remains the same as the unoptimized DP approach, as we still need to compute all `m * n` states. · **Space:** O(min(m, n)) - We only need space proportional to the length of the smaller array to store DP rows.
**Pros:** Most space-efficient solution.; Maintains the optimal O(m * n) time complexity.; Highly practical for interviews and competitive programming.
**Cons:** The implementation can be slightly more complex to manage the indices and the two arrays correctly.
### Explanation
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.

```java
class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        // To optimize space, we want the smaller array to determine the DP array size.
        if (m < n) {
            return maxDotProduct(nums2, nums1); // Swap arrays
        }
        // Now, m >= n.

        int[] prev_dp = new int[n];
        // Initialize prev_dp for the first row (i=0)
        for (int j = 0; j < n; j++) {
            prev_dp[j] = nums1[0] * nums2[j];
            if (j > 0) {
                prev_dp[j] = Math.max(prev_dp[j], prev_dp[j - 1]);
            }
        }

        for (int i = 1; i < m; i++) {
            int[] curr_dp = new int[n];
            for (int j = 0; j < n; j++) {
                int product = nums1[i] * nums2[j];
                
                int take_both = product;
                if (j > 0) {
                    take_both += Math.max(0, prev_dp[j - 1]);
                }
                
                curr_dp[j] = take_both;
                
                // Max with skipping nums1[i] (value from previous row, same column)
                curr_dp[j] = Math.max(curr_dp[j], prev_dp[j]);
                
                // Max with skipping nums2[j] (value from current row, previous column)
                if (j > 0) {
                    curr_dp[j] = Math.max(curr_dp[j], curr_dp[j - 1]);
                }
            }
            prev_dp = curr_dp; // Current row becomes previous for the next iteration
        }

        return prev_dp[n - 1];
    }
}
```
*Note: The provided code snippet has a slightly more optimized initialization for clarity and correctness, handling the first row separately before the main loop.*
### Algorithm
- 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.

# Solutions
### Java

```java
class Solution {
public
  int maxDotProduct(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[][] dp = new int[m + 1][n + 1];
    for (int[] e : dp) {
      Arrays.fill(e, Integer.MIN_VALUE);
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        dp[i][j] = Math.max(dp[i][j], Math.max(0, dp[i - 1][j - 1]) +
                                          nums1[i - 1] * nums2[j - 1]);
      }
    }
    return dp[m][n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxDotProduct(vector<int> &nums1, vector<int> &nums2) {
    int m = nums1.size(), n = nums2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        int v = nums1[i - 1] * nums2[j - 1];
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        dp[i][j] = max(dp[i][j], max(0, dp[i - 1][j - 1]) + v);
      }
    }
    return dp[m][n];
  }
};

```

### Python

```python
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int: m, n = len(nums1), len(nums2) dp = [[- inf] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): v = nums1[i - 1] * nums2[j - 1] dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], max(dp[i - 1][j - 1], 0) + v) return dp[- 1][- 1]

```