原文链接: https://leetcode-cn.com/problems/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.

 

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] 不是。

 

示例 1：

输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出：18
解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。

示例 2：

输入：nums1 = [3,-2], nums2 = [2,-6,7]
输出：21
解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。

示例 3：

输入：nums1 = [-1,-1], nums2 = [1,1]
输出：-1
解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。

 

提示：

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 100

 

点积：

定义 a = [a1, a2,…, an] 和 b = [b1, b2,…, bn] 的点积为：



这里的 Σ 指示总和符号。

通过代码

高赞题解

题意

本题就是求两个子序列点积的最大值。题意很明确，直接说解法。
很显然这题用dp做，但是状态转移方程怎么写，dp[i][j]代表什么意思，依然是一个值得写一下的问题。

首先我们考虑dp[i][j]代表什么意思。

dp[i][j]的含义

第一种想法：
dp[i][j]的含义是以nums1[i]和nums2[j]结尾的子序列的最大点积。
第二种想法：
dp[i][j]的含义是到nums1[i]和nums2[j]为止的子序列的最大点积。

这两种是不一样的：
第一种想法一定要包含nums1[i]和nums2[j]，因为以它们结尾。
但是第二种想法就没有这个限制，以谁结尾无所谓，最主要是大。

我们应该使用第二种，具体原因是因为状态转移方程。

状态转移方程

第一种想法的状态转移方程怎么写呢？

dp[i][j]=max(nums1[i]*nums2[j] , nums1[i]*nums2[j]+ maxVal);  

首先我们知道nums1[i]*nums2[j]这个值在第一种想法中是一定要有的。
接下来我们可以选择只有这两项或者包含前面的子序列点积最大值：
假如只有这两项，那么就什么都不加；假如也包含前面的就加上前面子序列点积的最大值maxVal。

来算一下时间复杂度：
首先算n^2个dp值
在每次dp计算中都要找到前面子序列点积的最大值，又要花费n^2的时间
所以时间复杂度为n^4,(500)^4是超时的

第二种想法的状态转移方程怎么写呢？
第二种可以选择nums1[i]和nums2[j]，所以我们可以通过这个来写状态转移方程：
(其实对于子序列的很多dp题来讲，都可以使用选不选来写状态转移方程)

1.选择nums1[i]和nums2[j]

1.1不选择前面的 dp[i][j]=nums1[i]*nums2[j]
1.2也选择前面的 dp[i][j]=max(dp[i][j],nums1[i]*nums2[j]+dp[i-1][j-1])
因为dp[i][j]是截止到nums1[i]和nums2[j]中的最大点积，所以只需要dp[i-1][j-1]就可以了  
事实上从这里可以看出想法一就是想法二的情况之一

2.选择nums1[i],不选择nums2[j]

等价于dp[i][j-1]
dp[i][j]=max(dp[i][j],dp[i][j-1])

3.不选择nums1[i],选择nums2[j]

等价于dp[i-1][j]
dp[i][j]=max(dp[i][j],dp[i-1][j])

4.？？？

聪明的你肯定知道了
状态方程你来写吧:dp[i][j]=max(dp[i][j],???)

代码

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int sz1=nums1.size(),sz2=nums2.size();
        vector<vector<int>> dp(sz1+1,vector<int>(sz2+1,-1e8));

        for(int i=1;i<=sz1;i++){
            for(int j=1;j<=sz2;j++){
                //1.1
                dp[i][j]=nums1[i-1]*nums2[j-1];
                //1.2
                dp[i][j]=max(dp[i][j],nums1[i-1]*nums2[j-1]+dp[i-1][j-1]);
                //2
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
                //3
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
                //4
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
            }
        }
        return dp[sz1][sz2];
    }
};

哦，对，求个赞

有疑问评论区可以交流，看到一定回

统计信息

通过次数	提交次数	AC比率
5725	12910	44.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言