Problem Statement in English

You’re given two integer arrays nums1 and nums2. Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A dot product for example of 2 sequences is basically the sum of products of elements at the same index.

Approach

You simply have to brute force it. But atleast we can cache the results of subproblems to avoid recomputation.

Another important point to note is that we have to ensure that we pick atleast one element from both arrays. So, when we reach the end of either array, we return negative infinity to avoid invalid subsequences. Otherwise, you end up returning 0, which fails when test cases have negative numbers in them.

In general, we have 4 choices at each step:

  1. Pick both elements from nums1 and nums2 at the current indices, and stop.
  2. Pick both elements from nums1 and nums2 at the current indices, and proceed.
  3. Skip the current element in nums2 and proceed.
  4. Skip the current element in nums1 and proceed.

And that’s it! It’s a really short piece of code.

Solution in Python


class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        N1 = len(nums1)
        N2 = len(nums2)

        @cache
        def dp(i, j):
            if i == N1 or j == N2:
                return -inf

            return max(
                nums1[i] * nums2[j],
                nums1[i] * nums2[j] + dp(i + 1, j + 1),
                dp(i, j + 1),
                dp(i + 1, j))

        return dp(0, 0)

Complexity

  • Time: $O(N1 \times N2)$
    Since we have two parameters i and j which can take N1 and N2 values respectively, we have a total of N1 * N2 unique states that can be computed and cached.

  • Space: $O(N1 \times N2)$
    Since the cache will store results for N1 * N2 unique states.

Mistakes I Made

I had also allowed for neither index to be chosen, and be skipped instead, which returned 0 when there there were negative numbers in the arrays. This was fixed by returning negative infinity when we reach the end of either array.

And we are done.