#1458

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Max Dot Product of Two Subsequences

Solve Max Dot Product of Two Subsequences with state transition dynamic programming that enforces a non-empty pairing despite negative products.

array dynamic programming

Problem Statement

You are given two integer arrays, nums1 and nums2. Pick one non-empty subsequence from each array so that both chosen subsequences have the same length, then maximize their dot product. Because elements must stay in original order, every decision is really about matching or skipping positions across the two arrays.

This problem is harder than standard subsequence DP because the optimal answer may be negative, so returning 0 for an empty choice is wrong. For example, when one array is all negative and the other is all positive, the best valid result can still be a single negative product, which means the DP must represent only valid non-empty selections.

Examples

Example 1

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]

Output: 18

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

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

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

Solution Approach

Define the DP state around suffixes

Let dp[i][j] be the maximum dot product achievable using non-empty subsequences taken from nums1 starting at index i and nums2 starting at index j. This suffix-based state matches the real choices in the problem: either pair nums1[i] with nums2[j], skip nums1[i], or skip nums2[j]. That framing keeps the transition local and avoids tracking subsequence length explicitly.

Use a transition that can start fresh or extend

At each state, compute product = nums1[i] * nums2[j]. Then compare four outcomes: take only this pair, extend a previous valid subsequence with product + max(0, dp[i+1][j+1]) in bottom-up form, skip nums1[i], or skip nums2[j]. The key detail is that the current pair must be allowed to start a new subsequence by itself, because extending from an invalid or harmful state would miss cases where one pair is the entire optimal answer.

Initialize for negative answers and optimize space if needed

Initialize unreachable states with a very small number instead of 0, since 0 would incorrectly act like an empty subsequence. A full O(mn) table is straightforward for lengths up to 500, and a rolling-row optimization can reduce space to O(n) if desired. The important correctness point is preserving the non-empty constraint while scanning the grid from bottom-right to top-left.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With m = nums1.length and n = nums2.length, the standard state transition DP fills an m by n table once, so time complexity is O(mn). The usual implementation uses O(mn) space for the table, while a rolling-row version reduces space to O(n) because each state only depends on the current row, the next row, and the diagonal next state.

What Interviewers Usually Probe

They ask how your DP prevents choosing empty subsequences when every product is negative.
They push on why the transition must compare taking the current pair alone versus extending dp[i+1][j+1].
They ask whether the same recurrence still works when zeros appear and when one strong pair beats every longer subsequence.

Common Pitfalls or Variants

Common pitfalls

Initializing DP with 0 and accidentally allowing an empty subsequence to beat valid negative answers.
Using a longest-common-subsequence style transition without the take-current-pair-alone case, which misses single-pair optima.
Forgetting that skipping is allowed independently in either array, so the DP must compare skip nums1 and skip nums2 at every state.

Follow-up variants

Return the actual subsequences that produce the maximum dot product instead of only the score.
Restrict the solution to subsequences of exactly k matched pairs, which adds a length dimension to the DP.
Change the objective to minimum dot product, which flips the transition logic and changes which negative states are desirable.

FAQ

What is the core pattern in Max Dot Product of Two Subsequences?

The core pattern is state transition dynamic programming on two indices. Each state decides whether to pair the current elements, skip in nums1, or skip in nums2, while enforcing that at least one pair is chosen.

Why is this problem not solved by a standard subsequence DP that uses 0 as the base answer?

Because 0 represents taking nothing, which is illegal here. If every valid pairing is negative, a 0-initialized DP will incorrectly prefer the empty choice over the required non-empty subsequences.

Why do we compare the current product alone against extending the diagonal DP state?

Sometimes the best answer starts at the current pair, and extending a previous subsequence would only make it worse. Comparing product alone with product plus the diagonal state captures both starting fresh and continuing an existing matched subsequence.

Can Max Dot Product of Two Subsequences be solved in O(mn)?

Yes. There are m times n index pairs, and each state does constant work from nearby states, so the DP runs in O(mn) time.

What edge case most often breaks correct solutions for LeetCode 1458?

The biggest failure mode is all-negative or sign-opposed inputs where the best valid result is still negative. Any solution that silently allows an empty subsequence will fail that case.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the maximum dot product of two subsequences formed by the first $i$ elements of $\textit{nums1}$ and the first $j$ elements of $\textit{nums2}$. Initially, $f[i][j] = -\infty$.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#1463 cherry pickup ii #1449 form largest integer with digits that add up to target #1467 probability of a two boxes having the same number of distinct balls