Max Dot Product Between Two Subsequences

Hard
582.

Max Dot Product Between Two Subsequences

Max Dot Product Between Two Subsequences is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDotProduct = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Both subsequences must be non-empty, so the answer can be negative — you cannot start the table at 0.

  2. Hint 2

    dp[i][j] is the best dot product using the prefixes nums1[0..i) and nums2[0..j), with at least one pair chosen.

  3. 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

  1. Let dp[i][j] be the best dot product over the prefixes, requiring at least one pair.
  2. Compute prod = nums1[i-1] * nums2[j-1].
  3. The candidates are: prod on its own; prod + dp[i-1][j-1] but only if that earlier value is positive; dp[i-1][j]; and dp[i][j-1].
  4. 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