1458. Max Dot Product of Two Subsequences

Problem Description

In this problem, we are given two integer arrays nums1 and nums2. We need to find the maximum dot product between non-empty subsequences of nums1 and nums2 that have the same length. A subsequence is derived from the original array by potentially removing some elements without changing the order of the remaining elements. The dot product of two sequences of the same length is the sum of the pairwise products of their corresponding elements.

To illustrate, if we have a subsequence [a1, a2, a3, ..., ai] from nums1 and [b1, b2, b3, ..., bi] from nums2, the dot product is a1*b1 + a2*b2 + a3*b3 + ... + ai*bi.

Our goal is to find such subsequences from nums1 and nums2 that when we calculate their dot product, we get the maximum possible value.

Intuition

The intuition behind the solution comes from recognizing that this problem can be solved optimally by breaking it down into simpler subproblems. This is a hint that dynamic programming might be a useful approach. More specifically, we can use a 2D dynamic programming table dp where dp[i][j] represents the maximum dot product between the first i elements of nums1 and the first j elements of nums2.

When we compute the entry dp[i][j], we consider the following possibilities to maximize our result:

1. dp[i - 1][j] — the maximum dot product without including the current element from nums1.
2. dp[i][j - 1] — the maximum dot product without including the current element from nums2.
3. dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1] — the maximum dot product including the current elements from both nums1 and nums2.
4. If dp[i - 1][j - 1] is less than 0, we only consider the product nums1[i - 1] * nums2[j - 1] because we would not want to diminish our result by adding a negative dot product from previous elements.

By computing the maximum of these options at each entry of the dp table, we ensure that we have considered all possibilities and end up with the maximum dot product of subsequences of the same length from nums1 and nums2.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to this problem involves using a 2D dynamic programming approach, which is a common pattern when dealing with problems of sequences and subproblems that depend on previous decisions.

We start by creating a 2D array dp with dimensions (m + 1) x (n + 1), where m is the length of nums1 and n is the length of nums2. We use m + 1 and n + 1 because we want to have an extra row and column to handle the base cases where the subsequence length is zero from either of the arrays. We initialize all values in the dp array to negative infinity (-inf) to represent the minimum possible dot product.

The dynamic programming algorithm iteratively fills the dp array as follows:

1. We loop over each possible subsequence length for nums1 (denoted by i) and nums2 (denoted by j) starting from 1 because index 0 is the base case representing an empty subsequence.
2. For each i, j pair, we calculate the dot product of the last elements v by multiplying nums1[i - 1] * nums2[j - 1].
3. We then fill in dp[i][j] by taking the maximum of:
   • dp[i - 1][j]: The max dot product without including nums1[i - 1];
   • dp[i][j - 1]: The max dot product without including nums2[j - 1];
   • max(dp[i - 1][j - 1], 0) + v: The max dot product including the current elements of both arrays. We use max(dp[i - 1][j - 1], 0) because if the previous dot product is negative, we would get a better result by just taking the current product v.

The reason we initialize with negative infinity and consider the max(dp[i-1][j-1], 0) in our recurrence is to ensure that we do not forcefully include negative products that would decrease the total maximum dot product. However, we need to include at least one pair of elements from both subsequences, as the result cannot be an empty subsequence according to the problem statement.

After filling the dp array, the last cell dp[m][n] contains the maximum dot product of non-empty subsequences of nums1 and nums2.

Here is the code snippet again that reflects this approach:

1class Solution:
2    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
3        m, n = len(nums1), len(nums2)
4        dp = [[-inf] * (n + 1) for _ in range(m + 1)]
5        for i in range(1, m + 1):
6            for j in range(1, n + 1):
7                v = nums1[i - 1] * nums2[j - 1]
8                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], max(dp[i - 1][j - 1], 0) + v)
9        return dp[-1][-1]

This code correctly solves the problem by leveraging the power of dynamic programming to optimize the process of finding the maximum dot product.

Example Walkthrough

Let's consider two small arrays for simplicity:

• nums1 = [2, 3]
• nums2 = [1, 2]

Using the dynamic programming approach described in the problem solution, we will create a 2D dp array with dimensions 3x3 (since nums1 and nums2 both have lengths 2, and we include an extra row and column for the base case):

1dp array initialization (values are -inf except dp[0][*] and dp[*][0] which could be set as 0 for base case):
2[  0, (-inf), (-inf) ]
3[ (-inf), (-inf), (-inf) ]
4[ (-inf), (-inf), (-inf) ]

We start populating the dp array at dp[1][1]:

• At i = 1, j = 1:

  • nums1[i - 1] * nums2[j - 1] is 2 * 1 which equals 2.
  • The entries dp[i - 1][j], dp[i][j - 1], and dp[i - 1][j - 1] are all 0 as they refer to base cases.
  • We select the maximum: max(0, 0, 0 + 2) which is 2.
  • Now, dp[1][1] is updated to 2.

• At i = 1, j = 2:

  • nums1[i - 1] * nums2[j - 1] is 2 * 2 which equals 4.
  • We consider the maximum of dp[1][1], dp[1][0], and dp[0][1] + 4 which are 2, 0, and 4, respectively.
  • The maximum value is 4, so we update dp[1][2] to 4.

• At i = 2, j = 1:

  • nums1[i - 1] * nums2[j - 1] is 3 * 1 which equals 3.
  • We take the maximum of dp[2][0], dp[1][1], and 0 + 3 (since dp[i - 1][j - 1] is 0), which are 0, 2, and 3.
  • The maximum value is 3, so dp[2][1] is updated to 3.

• At i = 2, j = 2:

  • nums1[i - 1] * nums2[j - 1] is 3 * 2 which equals 6.
  • Now, we consider max(dp[2][1], dp[1][2], dp[1][1] + 6) which are 3, 4, and 8.
  • The maximum value is 8, so we update dp[2][2] to 8.

After finishing the iteration, the final dp array looks like this:

1[  0,    0,    0  ]
2[  0,    2,    4  ]
3[  0,    3,    8  ]

• The value dp[2][2] which is 8 represents the maximum dot product of non-empty subsequences of nums1 and nums2.

Thus, the maximum dot product obtained from the subsequences [2, 3] from nums1 and [1, 2] from nums2 is 8, which is the dot product of the two arrays. Since these arrays are both the full length of the originals and we are looking for any subsequences, this would indeed be the maximum dot product in this simple example.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(m * n), where m is the length of nums1 and n is the length of nums2. This is because there are two nested loops, each iterating through the elements of nums1 and nums2 respectively.

The space complexity of the code is also O(m * n). This is due to the allocation of a 2D array dp of size (m + 1) * (n + 1) to store the intermediate results for each pair of indices (i, j).

Learn more about how to find time and space complexity quickly using problem constraints.