Max Dot Product of Two Subsequences: 2D DP Pattern

You are given two arrays nums1 and nums2. You need to select a non-empty subsequence from each array (maintaining original order) so that the two subsequences have the same length, then compute the dot product of those two subsequences. Return the maximum dot product possible.

This is LeetCode 1458: Max Dot Product of Two Subsequences. It is a hard-level 2D DP problem that combines the structure of Longest Common Subsequence with the twist of maximizing a sum of products. If you have worked through Edit Distance or Longest Common Subsequence, the grid setup will feel familiar. The new challenge is deciding which pairs of elements to multiply together for maximum total value.

Why this problem matters

The max dot product problem sits at the intersection of two fundamental ideas: subsequence selection and optimization over pairs of sequences. In machine learning, dot products measure similarity between vectors. In interview settings, this problem tests whether you can extend the classic 2D subsequence DP pattern to handle a product-based objective rather than a simple count or distance.

What makes this problem tricky is the interaction between positive and negative numbers. Two large negatives multiplied together give a large positive, so you cannot just greedily pick the biggest elements. You need to consider every possible pairing and let the DP table propagate the best cumulative decision forward.

This problem also reinforces the "include or skip" decision framework that powers nearly every subsequence DP problem. At each cell (i, j), you decide whether to pair nums1[i] with nums2[j] and add their product to the best result from earlier, or skip one of the two elements. Once you internalize this three-way choice, you can adapt it to dozens of similar problems.

The key insight

At each position (i, j) in the DP table, you face three choices:

1. Pair them: multiply nums1[i] * nums2[j] and add it to the best dot product from dp[i-1][j-1] (if it was positive), or just take the product alone.
2. Skip nums1[i]: carry forward the best answer from dp[i-1][j].
3. Skip nums2[j]: carry forward the best answer from dp[i][j-1].

The recurrence is:

dp[i][j] = max(nums1[i] * nums2[j], dp[i-1][j-1] + nums1[i] * nums2[j], dp[i-1][j], dp[i][j-1])

The first option handles the case where pairing this single product alone is better than combining it with any previous result (which happens when dp[i-1][j-1] is negative). The second option extends a previous dot product by adding this new pair. The third and fourth options skip one element.

The solution

def max_dot_product(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[float('-inf')] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            product = nums1[i] * nums2[j]
            dp[i][j] = product

            if i > 0 and j > 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + product)
            if i > 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j])
            if j > 0:
                dp[i][j] = max(dp[i][j], dp[i][j - 1])

    return dp[m - 1][n - 1]

The table is m x n (not (m+1) x (n+1) like edit distance) because there is no meaningful "empty subsequence" state here. The problem requires at least one pair. We initialize every cell to negative infinity so that the maximum propagation works correctly even when all products are negative.

For each cell (i, j), we first compute the raw product nums1[i] * nums2[j]. Then we check whether extending a previous best by adding this product gives a better result. Finally, we check whether skipping one of the current elements (carrying forward from the row above or the column to the left) yields something better.

The answer sits in dp[m-1][n-1], which represents the maximum dot product using any subsequences from the full arrays.

Visual walkthrough

Here is the DP table being filled step by step for nums1 = [2, 1, -2, 5] and nums2 = [3, 0, -6]. Each cell stores the maximum dot product achievable using elements from nums1[0..i] and nums2[0..j].

The key moment is at dp[2][2]. Here, nums1[2]=-2 and nums2[2]=-6 produce a product of 12. On its own that is good, but the recurrence also considers dp[1][1] + (-2)*(-6) = 6 + 12 = 18, which is even better. This is the power of negative-times-negative: the DP found that pairing (2, 3) earlier for a product of 6, then pairing (-2, -6) for a product of 12, gives a total dot product of 18. That value propagates to dp[3][2] = 18 as the final answer.

Complexity analysis

Where m is the length of nums1 and n is the length of nums2. Every cell in the m x n table is filled exactly once with O(1) work per cell. The space can be optimized to O(n) by keeping only two rows, since each row depends only on the current row and the row directly above it.

The building blocks

1. The three-way decision at each cell

product = nums1[i] * nums2[j]
dp[i][j] = product
if i > 0 and j > 0:
    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + product)

This is the core of the problem. You either start a fresh dot product with just this pair, or extend the best previous dot product by adding this pair. The max ensures you never carry forward a negative accumulated value when starting fresh would be better.

2. Skip propagation

if i > 0:
    dp[i][j] = max(dp[i][j], dp[i - 1][j])
if j > 0:
    dp[i][j] = max(dp[i][j], dp[i][j - 1])

These two lines let the optimal answer "flow" through the table. If the best dot product does not involve nums1[i] or nums2[j], these lines carry the answer forward. This is the same mechanism that LCS uses with max(dp[i-1][j], dp[i][j-1]) when characters do not match.

Edge cases

• All positive in one array, all negative in the other: every product is negative, so the answer is the product with the smallest absolute value (the least negative single pair). The DP handles this naturally.
• Single element arrays: dp[0][0] = nums1[0] * nums2[0]. The answer is just the single product.
• One array much longer than the other: the DP table is rectangular, not square. The shorter dimension determines the maximum number of pairs.
• Zeros in the arrays: a product of zero is valid. If all other products are negative, pairing with a zero element gives 0, which is better.
• Large negative values: nums1[i] and nums2[j] can each be as low as -1000, so a single product can reach 1,000,000. The DP accumulates these correctly.

From understanding to recall

You now know how to set up the m x n DP table, how the three-way decision works at each cell, and why negative times negative creates opportunities. But understanding the recurrence on paper is different from writing it under time pressure. In an interview, you need to remember that this table does not use the (m+1) x (n+1) convention, that initialization is negative infinity, and that the "pair" option includes both starting fresh and extending a previous result.

The max dot product problem belongs to the same family as LCS and edit distance, but the objective function (maximizing a sum of products rather than counting matches or minimizing edits) changes the recurrence in subtle ways. Drilling this alongside the other 2D DP problems locks in the differences so you do not mix them up.

Related posts

• Edit Distance - The classic 2D string DP with insert, delete, and replace operations on the same grid structure.
• Longest Common Subsequence - The foundational 2D subsequence DP that this problem extends with product-based optimization.
• Interleaving String - Another 2D DP on two sequences, using boolean cells instead of numeric ones.

The 2D DP family shares the same grid skeleton, but each problem changes what the cells store and how the recurrence combines neighbors. Once you have solved a few of these, you start seeing the pattern before you even finish reading the problem.