Given two arrays nums1 and nums2.
Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.
A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).
Example 1:
Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6] Output: 18 Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2. Their dot product is (2*3 + (-2)*(-6)) = 18.
Example 2:
Input: nums1 = [3,-2], nums2 = [2,-6,7] Output: 21 Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2. Their dot product is (3*7) = 21.
Example 3:
Input: nums1 = [-1,-1], nums2 = [1,1] Output: -1 Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2. Their dot product is -1.
Constraints:
1 <= nums1.length, nums2.length <= 500-1000 <= nums1[i], nums2[i] <= 1000This approach involves using dynamic programming to store results of subproblems and avoid redundant calculations.
We define a recursive helper function that considers each element from both arrays and decides whether to include it in the subsequence or not. The dynamic programming table stores the maximum dot product up to the current indices.
This C implementation uses a 2D array dp where dp[i][j] stores the maximum dot product of subsequences up to the i-th index of nums1 and j-th index of nums2.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) where m and n are the sizes of the two arrays.
Space Complexity: O(m * n) for the dp table.
This approach involves using backtracking combined with memoization to efficiently enumerate possible subsequences, storing results for reused subsequence comparisons to enhance performance.
The memoization helps to prevent recalculating results for the same indices, transforming exponential time complexity to polynomial time complexity.
This C implementation uses a recursive helper function to explore each possible state of subsequences. The dp array is used to cache results of subproblems, reducing the need for redundant calculations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2. Although recursive, memoization reduces repeated work.
Space Complexity: O(m * n) for the memoization array.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(m * n) where m and n are the sizes of the two arrays. |
| Recursive Backtracking with Memoization | Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2. Although recursive, memoization reduces repeated work. |
Maximum Product of the Length of Two Palindromic Subsequences - Leetcode 2002 - Python • NeetCode • 19,930 views views
Watch 9 more video solutions →Practice Max Dot Product of Two Subsequences with our built-in code editor and test cases.
Practice on FleetCode