DEV Community

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

Posted on

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

#programming #cpp #javascript #python

Finding the most optimal way to pair numbers from two different sequences can feel like a puzzle. This problem challenges us to look beyond simple multiplication and find the best hidden sequences to maximize our result.

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 need to 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 , we have a few choices:

  1. Start a new product or extend a previous one: We calculate . If the previous best result was positive, we add it to our current product.
  2. Skip an element from the first array: Carry over the best result found so far without using , which is .
  3. Skip an element from the second array: Carry over the best result found so far without using , which is .

By considering these options, the grid gradually fills up with the maximum possible values, ultimately giving us the answer in the bottom-right cell.

Code Blocks

C++ 

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

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // Choice 1: Multiply current elements and potentially add previous max
                dp[i][j] = A[i] * B[j];
                if (i > 0 && j > 0) {
                    dp[i][j] += max(dp[i - 1][j - 1], 0);
                }

                // Choice 2: Is it better to skip the current element from A?
                if (i > 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }

                // Choice 3: Is it better to skip the current element from B?
                if (j > 0) {
                    dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};
Enter fullscreen mode Exit fullscreen mode

Python 

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        # Initialize a 2D array with 0s
        dp = [[0] * m for _ in range(n)]

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

                # Combine with previous best if it's positive
                if i > 0 and j > 0:
                    dp[i][j] = current_product + max(dp[i-1][j-1], 0)
                else:
                    dp[i][j] = current_product

                # Compare with best results excluding current elements
                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]
Enter fullscreen mode Exit fullscreen mode

JavaScript 

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

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            let currentProduct = A[i] * B[j];

            // Add previous best diagonal if it helps
            if (i > 0 && j > 0) {
                dp[i][j] = currentProduct + Math.max(dp[i - 1][j - 1], 0);
            } else {
                dp[i][j] = currentProduct;
            }

            // Check if skipping an element results in a larger value
            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];
};
Enter fullscreen mode Exit fullscreen mode

Key Takeaways

  • Subsequence vs. Subarray: Remember that subsequences do not need to be contiguous. This is why we can "skip" elements using dp[i-1][j] and dp[i][j-1].
  • The Power of : By using a table to store intermediate results, we avoid re-calculating the same possibilities multiple times, transforming an exponential problem into a manageable quadratic one.
  • Handling Negative Numbers: The logic max(dp[i-1][j-1], 0) is crucial. It allows us to decide if a previous subsequence actually improves our current product or if we should start fresh.

Final Thoughts

This problem is a classic example of how dynamic programming can optimize search spaces. In the real world, these types of algorithms are the backbone of Recommendation Systems (matching user interests to product tags) and Bioinformatics (comparing DNA sequences). Mastering this pattern will give you a significant advantage in interviews for companies that deal with large-scale data matching.

Top comments (0)