LeetCode 1458 Solution: Max Dot Product of Two Subsequences

Problem Overview

You are given two integer arrays nums1 and nums2.
Your task is to find the maximum dot product of non-empty subsequences from both arrays.

Dot Product Definition

If subsequence A = [a1, a2, ..., ak] and B = [b1, b2, ..., bk],
then:

dot(A, B) = a1*b1 + a2*b2 + ... + ak*bk

Key Constraints

• Subsequences must be non-empty
• Order must be preserved
• Arrays may contain negative numbers

---

Why This Problem Is Tricky

At first glance, this looks like a classic DP problem similar to:

• Longest Common Subsequence (LCS)
• Maximum Subarray problems

However, there is a critical twist:

If all possible dot products are negative, we still must pick at least one pair.

This means:

• We cannot default to 0
• We must carefully handle negative values

---

Intuition

At each position (i, j) in nums1 and nums2, we have three choices:

1. Pair nums1[i] with nums2[j]
2. Skip nums1[i]
3. Skip nums2[j]

The challenge is deciding when to start a new subsequence versus extending an existing one.

---

Dynamic Programming Approach

DP Definition

Let:

dp[i][j] = maximum dot product using subsequences
           from nums1[i:] and nums2[j:]

Transition

At position (i, j):

1. Take both elementstake = nums1[i] * nums2[j] + max(0, dp[i+1][j+1])
   • max(0, ...) ensures we don’t extend a negative subsequence
2. Skip one element skip1 = dp[i+1][j] skip2 = dp[i][j+1]
3. Choose the best dp[i][j] = max(take, skip1, skip2)

---

Base Case

When either array is exhausted:

dp[i][j] = -∞

Why?

• Because subsequences must be non-empty
• Returning 0 would incorrectly allow empty selections

---

Final Answer

The solution is stored at:

dp[0][0]

---

Time & Space Complexity

• Time: O(n * m)
• Space: O(n * m)
• Can be optimized to O(m) using rolling arrays

---

Python Implementation

class Solution:
    def maxDotProduct(self, nums1, nums2):
        n, m = len(nums1), len(nums2)
        NEG_INF = -10**18

        dp = [[NEG_INF] * (m + 1) for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                take = nums1[i] * nums2[j]
                if dp[i + 1][j + 1] != NEG_INF:
                    take += max(0, dp[i + 1][j + 1])

                dp[i][j] = max(
                    take,
                    dp[i + 1][j],
                    dp[i][j + 1]
                )

        return dp[0][0]

---

Example Walkthrough

Input

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

Best subsequences

[2, -2, 5] and [3, -6, ?] → 2*3 + (-2)*(-6) = 6 + 12 = 18

---

Key Takeaways

• This is a 2D DP problem inspired by LCS
• The biggest pitfall is handling all-negative cases
• Returning -∞ instead of 0 is essential
• max(0, dp[i+1][j+1]) allows safe extension of subsequences