Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A pair of prefixes can form its best dot product by pairing their last elements or skipping one of them. Pairing can either start a new nonempty choice or extend earlier paired subsequences. Starting fresh matters when an earlier product would reduce the result.

Approach

Let dp[i][j] be the best nonempty dot product from the two prefixes. Initialize all states to negative infinity so the empty choice cannot beat a negative valid answer. For each last-element product, maximize four options: that product alone, that product plus the diagonal state, skipping the first array's element, and skipping the second's. Return the full-prefix state. Diagonal extension preserves equal subsequence lengths and the original order in both arrays.

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        m = len(nums2)
        dp = [[-inf] * (m + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                dp[i][j] = max(
                    nums1[i - 1] * nums2[j - 1], # start new subs
                    dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1], # continue subs
                    dp[i - 1][j], # skip i - 1
                    dp[i][j - 1] # skip j - 1
                )

        return dp[-1][-1]

Complexity analysis

For lengths n = nums1.length and m = nums2.length, the table fills nm states in constant time each. Time and auxiliary space are both O(nm).