Max Dot Product of Two Subsequences - Solution & Explanation

Problem Overview: You are given two integer arrays. Pick a non-empty subsequence from each array so that their dot product is maximized. The subsequences must maintain original order, but you can skip elements. Negative values make the problem tricky because skipping everything except the best pair may still produce the optimal result.

Approach 1: Recursive Backtracking with Memoization (Time: O(n*m), Space: O(n*m))

Start with recursion that explores three choices at every pair of indices (i, j): take both elements and include their product, skip the element in the first array, or skip the element in the second array. The recursive relation becomes max(nums1[i] * nums2[j] + solve(i+1, j+1), solve(i+1, j), solve(i, j+1)). Since many states repeat, store results in a memo table keyed by (i, j). Memoization reduces exponential recursion to a manageable O(n*m) dynamic programming state space while preserving the intuitive recursive logic.

This approach works well when you want to reason about the decision tree first. Each state represents the best possible dot product using suffixes of the two arrays. Handling negative values is important: the product at the current step may start a new subsequence instead of extending the previous one.

Approach 2: Dynamic Programming with Memoization (Time: O(n*m), Space: O(n*m))

Model the problem as a classic dynamic programming state. Let dp[i][j] represent the maximum dot product using elements starting from index i in nums1 and j in nums2. For each pair, compute the product nums1[i] * nums2[j]. You either start a new subsequence with that product or extend the best subsequence from dp[i+1][j+1]. Also consider skipping elements via dp[i+1][j] or dp[i][j+1].

The recurrence becomes dp[i][j] = max(product, product + dp[i+1][j+1], dp[i+1][j], dp[i][j+1]). This guarantees the subsequence remains non-empty while accounting for negative combinations. Since every pair of indices is computed once, the complexity stays O(n*m). Arrays and index transitions make this a standard grid-style DP similar to problems on arrays and sequence alignment.

Recommended for interviews: Interviewers typically expect the dynamic programming formulation. Start by explaining the recursive decision process, then introduce memoization to eliminate repeated states. Showing the transition from recursion to DP demonstrates strong understanding of dynamic programming patterns and sequence comparison problems.