Skip to main content
Talentd

Max Dot Product of Two Subsequences - Solution & Explanation

HardArrayDynamic Programming20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given two integer arrays. Pick a non-empty subsequence from each array so that their dot product is maximized. The subsequences must maintain original order, but you can skip elements. Negative values make the problem tricky because skipping everything except the best pair may still produce the optimal result.

Approach 1: Recursive Backtracking with Memoization (Time: O(n*m), Space: O(n*m))

Start with recursion that explores three choices at every pair of indices (i, j): take both elements and include their product, skip the element in the first array, or skip the element in the second array. The recursive relation becomes max(nums1[i] * nums2[j] + solve(i+1, j+1), solve(i+1, j), solve(i, j+1)). Since many states repeat, store results in a memo table keyed by (i, j). Memoization reduces exponential recursion to a manageable O(n*m) dynamic programming state space while preserving the intuitive recursive logic.

This approach works well when you want to reason about the decision tree first. Each state represents the best possible dot product using suffixes of the two arrays. Handling negative values is important: the product at the current step may start a new subsequence instead of extending the previous one.

Approach 2: Dynamic Programming with Memoization (Time: O(n*m), Space: O(n*m))

Model the problem as a classic dynamic programming state. Let dp[i][j] represent the maximum dot product using elements starting from index i in nums1 and j in nums2. For each pair, compute the product nums1[i] * nums2[j]. You either start a new subsequence with that product or extend the best subsequence from dp[i+1][j+1]. Also consider skipping elements via dp[i+1][j] or dp[i][j+1].

The recurrence becomes dp[i][j] = max(product, product + dp[i+1][j+1], dp[i+1][j], dp[i][j+1]). This guarantees the subsequence remains non-empty while accounting for negative combinations. Since every pair of indices is computed once, the complexity stays O(n*m). Arrays and index transitions make this a standard grid-style DP similar to problems on arrays and sequence alignment.

Recommended for interviews: Interviewers typically expect the dynamic programming formulation. Start by explaining the recursive decision process, then introduce memoization to eliminate repeated states. Showing the transition from recursion to DP demonstrates strong understanding of dynamic programming patterns and sequence comparison problems.

Approach 1: Dynamic Programming with Memoization

This approach involves using dynamic programming to store results of subproblems and avoid redundant calculations.

We define a recursive helper function that considers each element from both arrays and decides whether to include it in the subsequence or not. The dynamic programming table stores the maximum dot product up to the current indices.

This C implementation uses a 2D array dp where dp[i][j] stores the maximum dot product of subsequences up to the i-th index of nums1 and j-th index of nums2.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m and n are the sizes of the two arrays.
Space Complexity: O(m * n) for the dp table.

Try this approach in the editor →

Approach 2: Recursive Backtracking with Memoization

This approach involves using backtracking combined with memoization to efficiently enumerate possible subsequences, storing results for reused subsequence comparisons to enhance performance.

The memoization helps to prevent recalculating results for the same indices, transforming exponential time complexity to polynomial time complexity.

This C implementation uses a recursive helper function to explore each possible state of subsequences. The dp array is used to cache results of subproblems, reducing the need for redundant calculations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2. Although recursive, memoization reduces repeated work.
Space Complexity: O(m * n) for the memoization array.

Try this approach in the editor →

Approach 3: Dynamic Programming

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

For f[i][j], we have the following cases:

  1. Do not select nums1[i-1] or do not select nums2[j-1], i.e., f[i][j] = max(f[i-1][j], f[i][j-1]);
  2. Select nums1[i-1] and nums2[j-1], i.e., f[i][j] = max(f[i][j], max(0, f[i-1][j-1]) + nums1[i-1] times nums2[j-1]).

The final answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Memoization

Time Complexity: O(m * n) where m and n are the sizes of the two arrays.
Space Complexity: O(m * n) for the dp table.

Recursive Backtracking with Memoization

Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2. Although recursive, memoization reduces repeated work.
Space Complexity: O(m * n) for the memoization array.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Backtracking with MemoizationO(n*m)O(n*m)When reasoning about the decision tree first and converting recursion into DP.
Dynamic Programming with MemoizationO(n*m)O(n*m)General optimal solution for interview and production scenarios.
Bottom-Up Dynamic ProgrammingO(n*m)O(n*m)Preferred when avoiding recursion or stack overhead.

Video Solution

Max Dot Product of Two Subsequences | Detailed | Simplified | Leetcode 1458 | codestorywithMIK • codestorywithMIK • 13,247 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Dot Product of Two Subsequences easy or hard?
Max Dot Product of Two Subsequences is categorized as a Hard problem because it combines subsequence selection with negative value handling and dynamic programming transitions. Correctly modeling the DP recurrence and ensuring the subsequence is non-empty makes it more challenging than standard DP problems.
Max Dot Product of Two Subsequences Python/Java solution
Python and Java implementations typically use recursion with memoization or a bottom-up DP table. Both implementations maintain a 2D structure storing results for index pairs, ensuring O(n*m) complexity while avoiding repeated calculations.
How to solve Max Dot Product of Two Subsequences in O(n*m)?
Use a DP table where dp[i][j] stores the best dot product starting at indices i and j. Compute the product nums1[i] * nums2[j] and compare four choices: start a new subsequence with the product, extend dp[i+1][j+1], skip nums1[i], or skip nums2[j]. Filling or memoizing these states ensures every combination is processed once.
What is the best approach for Max Dot Product of Two Subsequences?
Dynamic Programming is the most effective approach. Define a DP state dp[i][j] representing the maximum dot product using suffixes of the two arrays. Each state considers taking both elements, skipping from the first array, or skipping from the second. This reduces the problem to O(n*m) time and space.
Is Max Dot Product of Two Subsequences asked at Google/Amazon/Meta?
Dynamic programming problems involving subsequences and pairwise comparisons are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of DP state transitions, handling negative values, and optimizing recursive solutions.
What data structure is used in Max Dot Product of Two Subsequences?
The core data structure is a 2D dynamic programming table or memoization map indexed by two pointers. Arrays are used to represent the DP grid, where each cell stores the best dot product achievable from the corresponding indices.
What is the time complexity of Max Dot Product of Two Subsequences?
The optimal dynamic programming solution runs in O(n*m) time where n and m are the lengths of the two arrays. Each pair of indices is evaluated once. Space complexity is also O(n*m) for the memoization or DP table.

Ready to solve this problem?

Practice Max Dot Product of Two Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays