Problem Description

You are given two arrays of integers, nums1 and nums2. You need to select non-empty subsequences from both arrays (not necessarily contiguous, but order must be preserved), such that both subsequences are of the same length. Then, for each pair of corresponding elements in the chosen subsequences, multiply them together and sum the results. Your goal is to return the maximum possible dot product of any such pair of subsequences.

• Each element in a subsequence must be from the original array, and the order must be preserved.
• You cannot reuse elements: each is used at most once in a subsequence.
• Both subsequences must be non-empty and of the same length.
• There is guaranteed to be at least one valid answer (i.e., you can always select at least one pair of elements).

Constraints:

• 1 ≤ nums1.length, nums2.length ≤ 500
• -1000 ≤ nums1[i], nums2[j] ≤ 1000

Thought Process

At first glance, the problem seems to suggest checking every possible subsequence pair, multiplying their elements, and finding the maximum sum. However, this would be extremely inefficient because the number of subsequences grows exponentially with array size.

To optimize, we notice that the problem is similar to finding the best alignment between two sequences, where each alignment is a pair of subsequences (with order preserved) and the "score" is their dot product. This is reminiscent of problems like "Longest Common Subsequence" but with multiplication and maximization.

The challenge is handling negative numbers, as sometimes skipping negative products is better, but in some cases, a negative times a negative yields a positive result. We must carefully decide at each step whether to pair the current elements or skip one (or both) to maximize the total dot product.

Solution Approach

We use Dynamic Programming (DP) to efficiently compute the answer. Here's how:

1. Define the State:
   • Let dp[i][j] represent the maximum dot product that can be achieved from the first i elements of nums1 and the first j elements of nums2.
2. Transition:
   • At each position (i, j), we have three options:
     1. Pair nums1[i] with nums2[j] (start or continue a subsequence): nums1[i] * nums2[j] plus dp[i-1][j-1] if we want to continue.
     2. Skip nums1[i]: consider dp[i-1][j].
     3. Skip nums2[j]: consider dp[i][j-1].
     The maximum of these is our answer for dp[i][j].
   • To handle the requirement of non-empty subsequences, we ensure that the pairwise product is always considered, even if dp[i-1][j-1] is negative.
   • So, dp[i][j] = max(nums1[i] * nums2[j], nums1[i] * nums2[j] + dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
3. Initialization:
   • Since subsequences must be non-empty, we initialize dp with very negative numbers (e.g., -inf), so that we don't accidentally count empty subsequences.
4. Result:
   • The answer is dp[m-1][n-1] where m and n are the lengths of nums1 and nums2.

This DP approach ensures that for each pair of positions, we consider all possible ways to build up the best dot product, efficiently reusing previously computed results.

Example Walkthrough

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]

1. Let's walk through the DP table construction:
   • Pair 2 (from nums1) with 3 (from nums2): 2*3 = 6
   • Pair 5 with 3: 5*3 = 15
   • Pair 5 with -6: 5*(-6) = -30
   • Pair -2 with -6: -2*(-6) = 12
2. Try pairing subsequences:
   • Pair [2,5] with [3,-6]: 2*3 + 5*(-6) = 6 - 30 = -24
   • Pair [1,5] with [0,-6]: 1*0 + 5*(-6) = 0 - 30 = -30
   • Pair [2,-2,5] with [3,0,-6]: 2*3 + (-2)*0 + 5*(-6) = 6 + 0 - 30 = -24
   • Pair [-2,5] with [-6,3]: -2*(-6) + 5*3 = 12 + 15 = 27
3. The DP approach will find that the best possible dot product is 27 by pairing [-2,5] with [-6,3].

Time and Space Complexity

• Brute-force:
  • For each possible subsequence of nums1 and nums2 (exponential in size), check all alignments. This is O(2^m * 2^n) and infeasible for large arrays.
• DP Approach:
  • We fill a m x n DP table, so time complexity is O(mn), where m and n are the lengths of nums1 and nums2.
  • Space complexity is also O(mn) for the DP table. This is efficient and feasible given the constraints.

Summary

The Max Dot Product of Two Subsequences problem can be solved efficiently using dynamic programming. By carefully defining the state and transitions, we avoid redundant work and ensure that all valid subsequence pairings are considered. The key insight is to always consider the pairwise product at each step and use DP to track the best result so far, handling negative numbers and non-empty constraints gracefully. This approach is both elegant and practical for the problem's constraints.

Code Implementation

from math import inf

class Solution:
    def maxDotProduct(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        dp = [[-inf] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                prod = nums1[i] * nums2[j]
                dp[i][j] = prod
                if i > 0 and j > 0:
                    dp[i][j] = max(dp[i][j], prod + dp[i-1][j-1])
                if i > 0:
                    dp[i][j] = max(dp[i][j], dp[i-1][j])
                if j > 0:
                    dp[i][j] = max(dp[i][j], dp[i][j-1])
        return dp[m-1][n-1]
      

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MIN));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int prod = nums1[i] * nums2[j];
                dp[i][j] = prod;
                if (i > 0 && j > 0)
                    dp[i][j] = max(dp[i][j], prod + dp[i-1][j-1]);
                if (i > 0)
                    dp[i][j] = max(dp[i][j], dp[i-1][j]);
                if (j > 0)
                    dp[i][j] = max(dp[i][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
};
      

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int prod = nums1[i] * nums2[j];
                dp[i][j] = prod;
                if (i > 0 && j > 0)
                    dp[i][j] = Math.max(dp[i][j], prod + dp[i-1][j-1]);
                if (i > 0)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
                if (j > 0)
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}
      

var maxDotProduct = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = Array.from({length: m}, () => Array(n).fill(Number.NEGATIVE_INFINITY));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let prod = nums1[i] * nums2[j];
            dp[i][j] = prod;
            if (i > 0 && j > 0)
                dp[i][j] = Math.max(dp[i][j], prod + dp[i-1][j-1]);
            if (i > 0)
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
            if (j > 0)
                dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
        }
    }
    return dp[m-1][n-1];
};