🧗‍♂️Beginner-Friendly Guide 'Max Dot Product of Two Subsequences' – LeetCode 1458 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:

• Two arrays of integers, nums1 and nums2.

Your goal:

• Find the maximum dot product possible between non‑empty subsequences of the two arrays that have the same length.

Intuition

The core of this problem lies in dynamic programming. Since we are looking for subsequences, we decide at each step whether to include the product of the current numbers or skip them to find a better pair later.

We build a 2D grid where dp[i][j] represents the maximum dot product we can achieve using elements from the start of the arrays up to index i in the first array and index j in the second.

For every pair of indices (i, j), we have three choices:

1. Start a new product or extend a previous one – calculate A[i] * B[j]. If the previous best result dp[i‑1][j‑1] was positive, add it to the current product.
2. Skip the current element from the first array – carry over dp[i‑1][j].
3. Skip the current element from the second array – carry over dp[i][j‑1].

By considering these options, the grid gradually fills up with the maximum possible values, and the answer ends up in the bottom‑right cell.

Code Blocks

C++

class Solution {
public:
    int maxDotProduct(vector& A, vector& B) {
        int n = A.size(), m = B.size();
        vector> dp(n, vector(m));

        for (int i = 0; i  0 && j > 0) {
                    dp[i][j] += max(dp[i - 1][j - 1], 0);
                }

                // Choice 2: Skip current element from A
                if (i > 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }

                // Choice 3: Skip current element from B
                if (j > 0) {
                    dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

Python

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        dp = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                current_product = A[i] * B[j]

                if i > 0 and j > 0:
                    dp[i][j] = current_product + max(dp[i - 1][j - 1], 0)
                else:
                    dp[i][j] = current_product

                if i > 0:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j])
                if j > 0:
                    dp[i][j] = max(dp[i][j], dp[i][j - 1])

        return dp[n - 1][m - 1]

JavaScript

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxDotProduct = function (A, B) {
    const n = A.length;
    const m = B.length;
    const dp = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i  0 && j > 0) {
                dp[i][j] = currentProduct + Math.max(dp[i - 1][j - 1], 0);
            } else {
                dp[i][j] = currentProduct;
            }

            if (i > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
            if (j > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n - 1][m - 1];
};

Key Takeaways

• Subsequence vs. Subarray: Subsequence elements need not be contiguous, which is why we can “skip” elements using dp[i‑1][j] and dp[i][j‑1].
• Dynamic Programming Power: Storing intermediate results in a table transforms an exponential‑time problem into a manageable quadratic one.
• Handling Negative Numbers: The expression max(dp[i‑1][j‑1], 0) decides whether a previous subsequence improves the current product or if we should start fresh.

Final Thoughts

This problem illustrates how dynamic programming can efficiently explore large search spaces. Similar techniques are used in recommendation systems (matching user interests to product tags) and bioinformatics (comparing DNA sequences). Mastering this pattern provides a strong advantage in technical interviews that involve large‑scale data matching.