1458. Max Dot Product of Two Subsequences LeetCode Solution
In this guide, you will get 1458. Max Dot Product of Two Subsequences LeetCode Solution with the best time and space complexity. The solution to Max Dot Product of Two Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Max Dot Product of Two Subsequences
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.
1458. Max Dot Product of Two Subsequences LeetCode Solution in C++
class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
// dp[i][j] := the maximum dot product of the two subsequences nums[0..i)
// and nums2[0..j)
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
dp[i + 1][j + 1] = max({dp[i][j + 1], dp[i + 1][j],
max(0, dp[i][j]) + nums1[i] * nums2[j]});
return dp[m][n];
}
}; /* code provided by PROGIEZ */
1458. Max Dot Product of Two Subsequences LeetCode Solution in Java
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
final int m = nums1.length;
final int n = nums2.length;
// dp[i][j] := the maximum dot product of the two subsequences nums[0..i)
// and nums2[0..j)
int[][] dp = new int[m + 1][n + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MIN_VALUE));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
dp[i + 1][j + 1] = Math.max(Math.max(dp[i][j + 1], dp[i + 1][j]),
Math.max(0, dp[i][j]) + nums1[i] * nums2[j]);
return dp[m][n];
}
} // code provided by PROGIEZ
1458. Max Dot Product of Two Subsequences LeetCode Solution in Python
class Solution:
def maxDotProduct(self, A: list[int], B: list[int]) -> int:
m = len(A)
n = len(B)
# dp[i][j] := the maximum dot product of the two subsequences nums[0..i)
# and nums2[0..j)
dp = [[-math.inf] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j],
max(0, dp[i][j]) + A[i] * B[j])
return dp[m][n] # code by PROGIEZ
