Max Dot Product of Two Subsequences

Max Dot Product of Two Subsequences

What is this problem about?

The Max Dot Product of Two Subsequences problem gives you two arrays of integers, nums1 and nums2. You need to select a non-empty subsequence from nums1 and a non-empty subsequence of the exact same length from nums2. The goal is to maximize the dot product of these two subsequences. The dot product is the sum of the products of their corresponding elements.

Why is this asked in interviews?

This is a Hard-level Dynamic Programming question. Interviewers ask it because it is an advanced variation of the Longest Common Subsequence (LCS) template. It tests your ability to handle negative numbers in DP calculations. Unlike standard LCS where "doing nothing" results in a score of 0, here, multiplying two negative numbers creates a positive score, but you must ensure the subsequences are non-empty.

Algorithmic pattern used

The problem utilizes 2D Dynamic Programming. We define dp[i][j] as the maximum dot product using prefixes nums1[0..i] and nums2[0..j]. For every pair of elements (nums1[i], nums2[j]), their product is val = nums1[i] * nums2[j]. The optimal choice for dp[i][j] is the maximum of:

1. Just val (starting a brand new subsequence from here).
2. val + dp[i-1][j-1] (appending to the best previous valid subsequence).
3. dp[i-1][j] (ignoring nums1[i]).
4. dp[i][j-1] (ignoring nums2[j]).

Example explanation

nums1 = [2, 1, -2, 5], nums2 = [3, 0, -6] Let's build the DP logic:

• Consider -2 and -6. Their product is 12.
• Consider 5 and 3. Product is 15. If we matched 2 with 3 (product 6), we could then match -2 with -6 (product 12). Total dot product: $6 + 12 = 18$. If we match 5 with -6, the product is -30. We would rather ignore one of them. The DP matrix systematically explores skipping vs. matching. By allowing a state to just be nums1[i] * nums2[j] without adding previous negative DP states, we cleanly restart sequences that fell below zero. The maximum overall DP cell holds 18.

Common mistakes candidates make

The biggest trap is the "non-empty" requirement. If you initialize the DP matrix with 0s (like you do in LCS), the algorithm will return 0 when the best actual dot product is a negative number (e.g., nums1 = [-1], nums2 = [1], answer is -1). You must initialize your DP matrix with negative infinity or carefully handle base cases to ensure a valid product of at least one pair is always taken.

Interview preparation tip

When modifying the LCS template for the Max Dot Product coding problem, remember the "fresh start" rule. In standard string DP, you either add 1 or take the max of skipping. Here, because values can be negative, you must explicitly allow the DP state to equal just the current product nums1[i] * nums2[j]. This effectively "severs" any toxic, negative historical chains.