Max Dot Product of Two Subsequences
Problem
Given two integer arrays nums1 and nums2, pick a non-empty subsequence from each so that both picks have the same length, then pair them up in order. The score is the dot product: the sum of the element-wise products. Return the maximum score possible.
A subsequence keeps the original order but may skip elements. Arrays have up to 500 elements with values in [−1000, 1000], so negatives matter — sometimes the best you can do is a single least-bad pair.
nums1 = [2,1,-2,5], nums2 = [3,0,-6]18def max_dot_product(nums1, nums2):
m, n = len(nums1), len(nums2)
NEG = float("-inf")
dp = [[NEG] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
p = nums1[i - 1] * nums2[j - 1]
best = p + max(0, dp[i - 1][j - 1])
best = max(best, dp[i - 1][j])
best = max(best, dp[i][j - 1])
dp[i][j] = best
return dp[m][n]function maxDotProduct(nums1, nums2) {
const m = nums1.length, n = nums2.length;
const NEG = -Infinity;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(NEG));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const p = nums1[i - 1] * nums2[j - 1];
let best = p + Math.max(0, 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[m][n];
}int maxDotProduct(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
long NEG = Long.MIN_VALUE / 4;
long[][] dp = new long[m + 1][n + 1];
for (long[] row : dp) Arrays.fill(row, NEG);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
long p = (long) nums1[i - 1] * nums2[j - 1];
long best = p + Math.max(0, 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[m][n];
}int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
const long long NEG = -1e18;
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, NEG));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
long long p = (long long) nums1[i - 1] * nums2[j - 1];
long long best = p + max(0LL, dp[i - 1][j - 1]);
best = max(best, dp[i - 1][j]);
best = max(best, dp[i][j - 1]);
dp[i][j] = best;
}
}
return dp[m][n];
}Explanation
This is the LCS grid in disguise. Walk both arrays with indices i and j, and let dp[i][j] be the best dot product achievable using only the first i numbers of nums1 and the first j of nums2. At each cell there are the classic three moves: pair the two current numbers, skip the current number of nums1, or skip the current number of nums2.
Two twists separate it from LCS. First, both subsequences must be non-empty, so the borders of the table start at −∞ instead of 0 — an empty pairing is not a legal answer. Second, products can be negative, so a previous chain is only worth extending when it helps: the pair option is p + max(0, dp[i−1][j−1]) where p = nums1[i−1]·nums2[j−1]. The max(0, ·) lets the pair stand alone (start fresh) whenever the best previous pairing is negative or −∞.
The full transition is dp[i][j] = max(p + max(0, dp[i−1][j−1]), dp[i−1][j], dp[i][j−1]). The two skip options copy the best result seen so far down and right, which is why the global answer ends up in the bottom-right cell dp[m][n].
On the default example nums1 = [2,1,-2,5], nums2 = [3,0,-6]: pairing 2 with 3 puts 6 in dp[1][1], and the skip moves carry that 6 along. At dp[3][3] the pair −2·−6 = 12 extends the carried 6 to 18. Pairing 5 with 3 alone gives 15 in the last row, but nothing beats 18, so dp[4][3] = 18 — exactly the subsequences [2,−2] and [3,−6].
The edge case the −∞ borders protect is when every possible product is negative, e.g. one array all positive and the other all negative. Then max(0, ·) never fires and every cell holds a single least-bad pair, which is the correct forced answer — a table of zeros would wrongly report 0.
Each of the m·n cells does constant work, so the time is O(m·n). The table costs O(m·n) space too (reducible to two rows since each cell only looks one row up).