本文共 2168 字,大约阅读时间需要 7 分钟。
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: 18Explanation: 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: 21Explanation: 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: -1Explanation: 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] <= 1000
题意:给你两个数组 nums1
和 nums2
。请你返回 nums1
和 nums2
中两个长度相同的 非空 子序列的最大点积。
数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。比方说,[2,3,5]
是 [1,2,3,4,5]
的一个子序列而 [1,5,3]
不是。
解法 动态规划
和LCS差不多的思路,这里分三种情况动态规划:不包含 nums1[i]
、不包含 nums2[j]
、包含 nums1[i], nums2[j]
(如果之前的最大点积为负数,则需要重新积累)。
class Solution { public: int maxDotProduct(vector & nums1, vector & nums2) { int m = nums1.size(), n = nums2.size(); //dp[i][j]表示nums1[0..i]与nums2[0..j]最大的点积 vector> dp(m, vector (n, INT_MIN)); dp[0][0] = nums1[0] * nums2[0]; //初始状态 for (int j = 1; j < n; ++j) dp[0][j] = max(dp[0][j - 1], nums1[0] * nums2[j]); for (int i = 1; i < m; ++i) dp[i][0] = max(dp[i - 1][0], nums2[0] * nums1[i]); //动态规划 for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), (dp[i - 1][j - 1] > 0 ? dp[i - 1][j - 1] : 0) + nums1[i] * nums2[j]); return dp[m - 1][n - 1]; }};
运行效率如下:
执行用时:32 ms, 在所有 C++ 提交中击败了75.80% 的用户内存消耗:12.7 MB, 在所有 C++ 提交中击败了63.70% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/117935941 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!