Max Dot Product of Two Subsequences solution and explanation
Google
9 more videos on this problem
Max Dot Product of Two Subsequences | Detailed | Simplified | Leetcode 1458 | codestorywithMIKcodestorywithMIK · 22:31 · 13K views
1458. Max Dot Product of Two Subsequences | Leetcode Daily - PythonLeetcode Daily · 7:19 · 1K views
1458. Max Dot Product of Two Subsequences (Leetcode Hard)Programming Live with Larry · 10:54 · 1K views
Dynamic Programming Unleashed: Max Dot Product of Two Subsequences PythonvanAmsen · 9:45 · 841 views
Daily Leetcode #2109: Jan 08, 2026 - 1458. Max Dot Product of Two SubsequencesProgramming Live with Larry · 6:33 · 683 views
Max Dot Product of Two Subsequences - Leetcode 1458 - PythonTim Huang · 7:11 · 609 views
Max Dot Product of Two Subsequences - Dynamic Programming - JAVA-1458 Leetcode Hard in 10 minsLeet Logics · 9:54 · 526 views
Daily Leetcode #1286: Oct 08, 2023 - 1458. Max Dot Product of Two SubsequencesProgramming Live with Larry · 8:45 · 468 views
Max Dot Product Of Two Subsequences - LeetCode 1458 - PythonAlpha-Code · 34:23 · 342 views
LeetCode1458: ✅ Max Dot Product of Two Subsequences, DPThe algorithm Architect · 13:20 · 299 views
The 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
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.
def maxDotProduct(nums1, nums2):
m, n = len(nums1), len(nums2)
dp = [[float('-inf')] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
prod = nums1[i - 1] * nums2[j - 1]
dp[i][j] = max(dp[i][j], prod)
dp[i][j] = max(dp[i][j], prod + dp[i - 1][j - 1] if i > 1 and j > 1 else prod)
dp[i][j] = max(dp[i][j], dp[i - 1][j])
dp[i][j] = max(dp[i][j], dp[i][j - 1])
return dp[m][n]
nums1 = [2, 1, -2, 5]
nums2 = [3, 0, -6]
print(maxDotProduct(nums1, nums2))import java.util.*;
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[] row : dp) Arrays.fill(row, Integer.MIN_VALUE);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int prod = nums1[i - 1] * nums2[j - 1];
dp[i][j] = Math.max(dp[i][j], prod);
dp[i][j] = Math.max(dp[i][j], prod + (i > 1 && j > 1 ? dp[i - 1][j - 1] : 0));
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums1 = {2, 1, -2, 5};
int[] nums2 = {3, 0, -6};
System.out.println(sol.maxDotProduct(nums1, nums2));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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 prod = nums1[i - 1] * nums2[j - 1];
dp[i][j] = max(dp[i][j], prod);
dp[i][j] = max(dp[i][j], prod + (i > 1 && j > 1 ? dp[i - 1][j - 1] : 0));
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
int main() {
vector<int> nums1 = {2, 1, -2, 5};
vector<int> nums2 = {3, 0, -6};
cout << maxDotProduct(nums1, nums2) << endl;
return 0;
}function maxDotProduct(nums1, nums2) {
const m = nums1.length, n = nums2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(-Infinity));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const prod = nums1[i - 1] * nums2[j - 1];
dp[i][j] = Math.max(dp[i][j], prod);
dp[i][j] = Math.max(dp[i][j], prod + (i > 1 && j > 1 ? dp[i - 1][j - 1] : 0));
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
const nums1 = [2, 1, -2, 5];
const nums2 = [3, 0, -6];
console.log(maxDotProduct(nums1, nums2));#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
return a > b ? a : b;
}
int maxDotProduct(int *nums1, int nums1Size, int *nums2, int nums2Size) {
int dp[501][501];
for (int i = 0; i <= nums1Size; i++) {
for (int j = 0; j <= nums2Size; j++) {
dp[i][j] = INT_MIN;
}
}
for (int i = 1; i <= nums1Size; i++) {
for (int j = 1; j <= nums2Size; j++) {
int prod = nums1[i-1] * nums2[j-1];
dp[i][j] = max(dp[i][j], prod + (i > 1 && j > 1 ? dp[i-1][j-1] : 0));
dp[i][j] = max(dp[i][j], dp[i-1][j]);
dp[i][j] = max(dp[i][j], dp[i][j-1]);
}
}
return dp[nums1Size][nums2Size];
}
int main() {
int nums1[] = {2, 1, -2, 5};
int nums2[] = {3, 0, -6};
int result = maxDotProduct(nums1, 4, nums2, 3);
printf("%d\n", result);
return 0;
}using System;
public 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 i = 0; i <= m; ++i)
for (int j = 0; j <= n; ++j)
dp[i, j] = int.MinValue;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int prod = nums1[i - 1] * nums2[j - 1];
dp[i, j] = Math.Max(dp[i, j], prod);
if (i > 1 && j > 1) dp[i, j] = Math.Max(dp[i, j], prod + dp[i - 1, j - 1]);
dp[i, j] = Math.Max(dp[i, j], dp[i - 1, j]);
dp[i, j] = Math.Max(dp[i, j], dp[i, j - 1]);
}
}
return dp[m, n];
}
public static void Main() {
int[] nums1 = {2, 1, -2, 5};
int[] nums2 = {3, 0, -6};
Solution sol = new Solution();
Console.WriteLine(sol.MaxDotProduct(nums1, nums2));
}
}The Python solution uses a list of lists as a dynamic programming table. It calculates the maximum dot product by iterating and updating the DP table, similar to C and C++ solutions.
Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2.
Space Complexity: O(m * n) due to the dp table.
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.
def maxDotProduct(nums1, nums2):
def dfs(i, j):
if i >= len(nums1) or j >= len(nums2):
return float('-inf')
if dp[i][j] > float('-inf'):
return dp[i][j]
prod = nums1[i] * nums2[j]
result = prod + dfs(i + 1, j + 1)
result = max(result, dfs(i + 1, j))
result = max(result, dfs(i, j + 1))
result = max(result, prod)
dp[i][j] = result
return dp[i][j]
dp = [[float('-inf')] * len(nums2) for _ in range(len(nums1))]
return dfs(0, 0)
nums1 = [2, 1, -2, 5]
nums2 = [3, 0, -6]
print(maxDotProduct(nums1, nums2))import java.util.*;
class Solution {
int[][] dp;
private int dfs(int[] nums1, int[] nums2, int i, int j) {
if (i >= nums1.length || j >= nums2.length) return Integer.MIN_VALUE / 2;
if (dp[i][j] != Integer.MIN_VALUE) return dp[i][j];
int product = nums1[i] * nums2[j];
int result = product + dfs(nums1, nums2, i + 1, j + 1);
result = Math.max(result, dfs(nums1, nums2, i + 1, j));
result = Math.max(result, dfs(nums1, nums2, i, j + 1));
result = Math.max(result, product);
dp[i][j] = result;
return dp[i][j];
}
public int maxDotProduct(int[] nums1, int[] nums2) {
dp = new int[nums1.length][nums2.length];
for (int[] row : dp) Arrays.fill(row, Integer.MIN_VALUE);
return dfs(nums1, nums2, 0, 0);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums1 = {2, 1, -2, 5};
int[] nums2 = {3, 0, -6};
System.out.println(sol.maxDotProduct(nums1, nums2));
}
}#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
vector<vector<int>> dp;
int dfs(const vector<int>& nums1, const vector<int>& nums2, int i, int j) {
if (i >= nums1.size() || j >= nums2.size()) return INT_MIN / 2;
if (dp[i][j] != INT_MIN) return dp[i][j];
int result = nums1[i] * nums2[j] + dfs(nums1, nums2, i + 1, j + 1);
result = max(result, dfs(nums1, nums2, i + 1, j));
result = max(result, dfs(nums1, nums2, i, j + 1));
result = max(result, nums1[i] * nums2[j]);
dp[i][j] = result;
return dp[i][j];
}
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
dp = vector<vector<int>>(nums1.size(), vector<int>(nums2.size(), INT_MIN));
return dfs(nums1, nums2, 0, 0);
}
int main() {
vector<int> nums1 = {2, 1, -2, 5};
vector<int> nums2 = {3, 0, -6};
cout << maxDotProduct(nums1, nums2) << endl;
return 0;
}function maxDotProduct(nums1, nums2) {
const memo = Array.from({ length: nums1.length }, () => Array(nums2.length).fill(-Infinity));
function dfs(i, j) {
if (i >= nums1.length || j >= nums2.length) return -Infinity;
if (memo[i][j] > -Infinity) return memo[i][j];
const prod = nums1[i] * nums2[j];
let result = prod + dfs(i + 1, j + 1);
result = Math.max(result, dfs(i + 1, j));
result = Math.max(result, dfs(i, j + 1));
result = Math.max(result, prod);
memo[i][j] = result;
return result;
}
return dfs(0, 0);
}
const nums1 = [2, 1, -2, 5];
const nums2 = [3, 0, -6];
console.log(maxDotProduct(nums1, nums2));#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
return a > b ? a : b;
}
int dp[501][501];
int dfs(int *nums1, int nums1Size, int *nums2, int nums2Size, int i, int j) {
if (i >= nums1Size || j >= nums2Size) return INT_MIN / 2;
if (dp[i][j] != INT_MIN) return dp[i][j];
int result = nums1[i] * nums2[j] + dfs(nums1, nums1Size, nums2, nums2Size, i + 1, j + 1);
result = max(result, dfs(nums1, nums1Size, nums2, nums2Size, i + 1, j));
result = max(result, dfs(nums1, nums1Size, nums2, nums2Size, i, j + 1));
result = max(result, nums1[i] * nums2[j]);
dp[i][j] = result;
return dp[i][j];
}
int maxDotProduct(int *nums1, int nums1Size, int *nums2, int nums2Size) {
for (int i = 0; i < nums1Size; i++)
for (int j = 0; j < nums2Size; j++)
dp[i][j] = INT_MIN;
return dfs(nums1, nums1Size, nums2, nums2Size, 0, 0);
}
int main() {
int nums1[] = {2, 1, -2, 5};
int nums2[] = {3, 0, -6};
int result = maxDotProduct(nums1, 4, nums2, 3);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
private int[,] dp;
private int Dfs(int[] nums1, int[] nums2, int i, int j) {
if (i >= nums1.Length || j >= nums2.Length) return int.MinValue / 2;
if (dp[i, j] != int.MinValue) return dp[i, j];
int prod = nums1[i] * nums2[j];
int result = prod + Dfs(nums1, nums2, i + 1, j + 1);
result = Math.Max(result, Dfs(nums1, nums2, i + 1, j));
result = Math.Max(result, Dfs(nums1, nums2, i, j + 1));
result = Math.Max(result, prod);
dp[i, j] = result;
return dp[i, j];
}
public int MaxDotProduct(int[] nums1, int[] nums2) {
dp = new int[nums1.Length, nums2.Length];
for (int i = 0; i < nums1.Length; i++)
for (int j = 0; j < nums2.Length; j++)
dp[i, j] = int.MinValue;
return Dfs(nums1, nums2, 0, 0);
}
public static void Main() {
int[] nums1 = {2, 1, -2, 5};
int[] nums2 = {3, 0, -6};
Solution sol = new Solution();
Console.WriteLine(sol.MaxDotProduct(nums1, nums2));
}
}This Python version explores indices recursively while storing calculated results in `dp`. The goal in each call is to decide whether to continue down the recursion tree with or without the current element pair.
Time Complexity: O(m * n) due to thorough caching, reducing redundant calculations.
Space Complexity: O(m * n) for the dp memory space storing results.
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:
- Do not select
nums1[i-1]or do not selectnums2[j-1], i.e.,f[i][j] = max(f[i-1][j], f[i][j-1]); - Select
nums1[i-1]andnums2[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.
function maxDotProduct(nums1: number[], nums2: number[]): number {
const m = nums1.length;
const n = nums2.length;
const f = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => -Infinity));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
const v = nums1[i - 1] * nums2[j - 1];
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
f[i][j] = Math.max(f[i][j], Math.max(0, f[i - 1][j - 1]) + v);
}
}
return f[m][n];
}func maxDotProduct(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
for j := range f[i] {
f[i][j] = math.MinInt32
}
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
v := nums1[i-1] * nums2[j-1]
f[i][j] = max(f[i-1][j], f[i][j-1])
f[i][j] = max(f[i][j], max(0, f[i-1][j-1])+v)
}
}
return f[m][n]
}impl Solution {
pub fn max_dot_product(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let m = nums1.len();
let n = nums2.len();
let mut f = vec![vec![i32::MIN; n + 1]; m + 1];
for i in 1..=m {
for j in 1..=n {
let v = nums1[i - 1] * nums2[j - 1];
f[i][j] = f[i][j].max(f[i - 1][j]).max(f[i][j - 1]);
f[i][j] = f[i][j].max(f[i - 1][j - 1].max(0) + v);
}
}
f[m][n]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2. |
| Recursive Backtracking with Memoization | Time Complexity: O(m * n) due to thorough caching, reducing redundant calculations. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Memoization | O(n*m) | O(n*m) | When reasoning about the decision tree first and converting recursion into DP. |
| Dynamic Programming with Memoization | O(n*m) | O(n*m) | General optimal solution for interview and production scenarios. |
| Bottom-Up Dynamic Programming | O(n*m) | O(n*m) | Preferred when avoiding recursion or stack overhead. |
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.