Max Dot Product Between Two Subsequences — Solution
Max Dot Product Between Two Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Max Dot Product Between Two Subsequences is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two arrays nums1 and nums2, pick a non-empty subsequence from each with the same length, and return the maximum possible dot product between them.
A subsequence keeps the original order but may skip elements.
Example 1
Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take [2,-2] and [3,-6]: 2·3 + (-2)·(-6) = 18.
Example 2
Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take [3] and [7].
Example 3
Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Every product is negative; the best is a single pair.
Constraints
1 <= nums1.length, nums2.length <= 500-1000 <= nums1[i], nums2[j] <= 1000
Hints for Max Dot Product Between Two Subsequences
Hint 1
Both subsequences must be non-empty, so the answer can be negative — you cannot start the table at 0.
Hint 2
dp[i][j]is the best dot product using the prefixesnums1[0..i)andnums2[0..j), with at least one pair chosen.Hint 3
At each cell, either pair the current elements (optionally on top of a positive earlier result) or skip one of them.
How to solve Max Dot Product Between Two Subsequences
A pairing DP, but with a twist: because both subsequences must be non-empty, the standard "start from zero" table would allow an empty pairing and lose negative-only cases. Pairing the current elements alone is always an option.
Approach
- Let
dp[i][j]be the best dot product over the prefixes, requiring at least one pair. - Compute
prod = nums1[i-1] * nums2[j-1]. - The candidates are:
prodon its own;prod + dp[i-1][j-1]but only if that earlier value is positive;dp[i-1][j]; anddp[i][j-1]. - Take the maximum and return
dp[n][m].
Why it works
Extending an earlier pairing is worth it only when that pairing contributes positively — otherwise starting fresh with just this product is better. Guarding on > 0 encodes exactly that, and keeps the all-negative case honest.
Complexity
- Time —
O(n · m) - Space —
O(n · m)
Pitfalls
- Initialising the table to 0 silently permits an empty subsequence, giving 0 for
[-1,-1]vs[1,1]instead of -1. - Adding
dp[i-1][j-1]unconditionally drags good pairs down with earlier negative totals. - The sentinel must be smaller than any achievable dot product — 500 pairs of ±1,000,000 bound it well below 1e15.
Reference solution
Python
from typing import List
def maxDotProduct(nums1: List[int], nums2: List[int]) -> int:
n, m = len(nums1), len(nums2)
NEG = -10 ** 15
dp = [[NEG] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
prod = nums1[i - 1] * nums2[j - 1]
best = prod
if dp[i - 1][j - 1] > 0:
best = max(best, prod + dp[i - 1][j - 1])
best = max(best, dp[i - 1][j], dp[i][j - 1])
dp[i][j] = best
return dp[n][m]Java
public static int maxDotProduct(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
long NEG = -1000000000000000L;
long[][] dp = new long[n + 1][m + 1];
for (long[] row : dp) Arrays.fill(row, NEG);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
long prod = (long) nums1[i - 1] * nums2[j - 1];
long best = prod;
if (dp[i - 1][j - 1] > 0) best = Math.max(best, prod + dp[i - 1][j - 1]);
best = Math.max(best, dp[i - 1][j]);
best = Math.max(best, dp[i][j - 1]);
dp[i][j] = best;
}
}
return (int) dp[n][m];
}C++
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int n = (int) nums1.size(), m = (int) nums2.size();
long long NEG = -1000000000000000LL;
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, NEG));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
long long prod = (long long) nums1[i - 1] * nums2[j - 1];
long long best = prod;
if (dp[i - 1][j - 1] > 0) best = max(best, prod + dp[i - 1][j - 1]);
best = max(best, dp[i - 1][j]);
best = max(best, dp[i][j - 1]);
dp[i][j] = best;
}
}
return (int) dp[n][m];
}JavaScript
var maxDotProduct = function(nums1, nums2) {
const n = nums1.length, m = nums2.length;
const NEG = -1e15;
const dp = [];
for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(NEG));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
const prod = nums1[i - 1] * nums2[j - 1];
let best = prod;
if (dp[i - 1][j - 1] > 0) best = Math.max(best, prod + dp[i - 1][j - 1]);
best = Math.max(best, dp[i - 1][j]);
best = Math.max(best, dp[i][j - 1]);
dp[i][j] = best;
}
}
return dp[n][m];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming