HardNo. 1458
Max Dot Product of Two Subsequences — LeetCode 1458 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given two arrays nums1 and nums2. Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.
Example
- 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.
Python solution
class Solution:
def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
f = [[-inf] * (n + 1) for _ in range(m + 1)]
for i, x in enumerate(nums1, 1):
for j, y in enumerate(nums2, 1):
v = x * y
f[i][j] = max(f[i - 1][j], f[i][j - 1], max(0, f[i - 1][j - 1]) + v)
return f[m][n]Complexity
- Time
- O(m × n)
- Space · auxiliary
- O(m × n)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1458. Max Dot Product of Two Subsequences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1463 | Cherry Pickup II | Hard |
| 1449 | Form Largest Integer With Digits That Add up to Target | Hard |
| 1467 | Probability of a Two Boxes Having The Same Number of Distinct Balls | Hard |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
Frequently asked questions
- How hard is LeetCode 1458. Max Dot Product of Two Subsequences?
LeetCode 1458. Max Dot Product of Two Subsequences is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1458. Max Dot Product of Two Subsequences?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 1458. Max Dot Product of Two Subsequences?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 1458. Max Dot Product of Two Subsequences cover?
LeetCode 1458. Max Dot Product of Two Subsequences is tagged Array and Dynamic Programming on LeetCode.