Leetcode Problem 1458. Max Dot Product of Two Subsequences

1458. Max Dot Product of Two Subsequences

Leetcode Solutions

Approach: Top-Down Dynamic Programming

  1. Handle special cases where all elements in one array are negative and all in the other are positive.
  2. Define the memoized function dp(i, j).
  3. If i == nums1.length or j == nums2.length, return 0.
  4. Calculate the dot product if we use the current numbers: use = nums1[i] * nums2[j] + dp(i + 1, j + 1).
  5. Return the maximum of use, dp(i + 1, j), and dp(i, j + 1).
  6. Call dp(0, 0) to get the answer to the original problem.
UML Thumbnail

Approach: Bottom-Up Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...