We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Dot Product of Two Subsequences

Number: 1569

Difficulty: Hard

Paid? No

Companies: Microsoft

Problem Description

Given two arrays nums1 and nums2, find the maximum dot product between non-empty subsequences (of equal length) selected from each array. A subsequence is formed by deleting some (or no) elements without reordering the remaining elements. Special care is needed when arrays contain all negative numbers.

Key Insights

  • The goal is to maximize the dot product between aligned elements of two subsequences.
  • Use dynamic programming to consider all pairs (i, j) where subsequences ending at nums1[i] and nums2[j] can be formed.
  • It is crucial to consider starting a new subsequence at (i, j) with just the product or extending an existing subsequence.
  • Skipping an element in one array could lead to a better result, so carry over the best value from previous states.
  • Handle negative values carefully since the product may be negative, and a "restart" might be beneficial.

Space and Time Complexity

Time Complexity: O(n * m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(n * m) due to the dp table used to store the maximum dot products.

Solution

We construct a dp table where dp[i][j] represents the maximum dot product possible using any subsequences ending at index i in nums1 and index j in nums2. For each dp[i][j]:

  • Compute the current product = nums1[i] * nums2[j].
  • Option 1: Start a new subsequence with this product.
  • Option 2: Extend a previously computed subsequence from dp[i-1][j-1] by adding the current product.
  • Also consider the best result from dp[i-1][j] (skipping nums1[i]) and dp[i][j-1] (skipping nums2[j]). The final answer resides in dp[n-1][m-1].

Code Solutions

# Python solution with detailed comments:

def maxDotProduct(nums1, nums2):
    n, m = len(nums1), len(nums2)
    # Initialize a 2D dp table with -infinity for handling negative values
    dp = [[float('-inf')] * m for _ in range(n)]
    
    # Base case: first cell is the product of the first elements
    dp[0][0] = nums1[0] * nums2[0]
    
    # Fill the first row (using only nums1[0])
    for j in range(1, m):
        product = nums1[0] * nums2[j]
        dp[0][j] = max(dp[0][j-1], product)
    
    # Fill the first column (using only nums2[0])
    for i in range(1, n):
        product = nums1[i] * nums2[0]
        dp[i][0] = max(dp[i-1][0], product)
    
    # Fill the rest of dp table
    for i in range(1, n):
        for j in range(1, m):
            product = nums1[i] * nums2[j]
            # Either start a new subsequence or extend the previous matching subsequence
            dp[i][j] = max(product, dp[i-1][j-1] + product)
            # Check if skipping current element from nums1 or nums2 yields better result
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])
    
    return dp[n-1][m-1]

# Example usage:
print(maxDotProduct([2, 1, -2, 5], [3, 0, -6]))  # Expected output: 18
← Back to All Questions