Hard

题目描述

给定两个数组 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] <= 1000

解题思路

这道题需要找到两个数组中长度相同的子序列，使得它们的点积最大。这是一个典型的动态规划问题。

思路分析：

我们可以定义 dp[i][j] 为考虑 nums1[0...i] 和 nums2[0...j] 中子序列的最大点积。对于每一对位置 (i, j)，我们有以下选择：

  1. 不选择当前元素：dp[i-1][j] 或 dp[i][j-1]
  2. 选择当前元素对：nums1[i] * nums2[j]，然后加上之前的最优解 dp[i-1][j-1]
  3. 只选择当前元素对作为新的开始：nums1[i] * nums2[j]

状态转移方程为：

dp[i][j] = max(
    dp[i-1][j],                              // 不选 nums1[i]
    dp[i][j-1],                              // 不选 nums2[j]
    nums1[i] * nums2[j],                     // 只选当前对
    dp[i-1][j-1] + nums1[i] * nums2[j]      // 选当前对并连接之前
)

需要注意边界条件的处理，当 i=0 或 j=0 时，只能选择单个元素对。

由于题目要求子序列非空，我们需要确保最终结果至少包含一对元素。

代码实现

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m, vector<int>(n));
        
        // 初始化第一行和第一列
        dp[0][0] = nums1[0] * nums2[0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = max(dp[i-1][0], nums1[i] * nums2[0]);
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = max(dp[0][j-1], nums1[0] * nums2[j]);
        }
        
        // 填充dp表
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int current = nums1[i] * nums2[j];
                dp[i][j] = max({
                    dp[i-1][j],                    // 不选nums1[i]
                    dp[i][j-1],                    // 不选nums2[j]
                    current,                       // 只选当前对
                    dp[i-1][j-1] + current        // 选当前对并连接
                });
            }
        }
        
        return dp[m-1][n-1];
    }
};

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0] * n for _ in range(m)]
        
        # 初始化第一行和第一列
        dp[0][0] = nums1[0] * nums2[0]
        for i in range(1, m):
            dp[i][0] = max(dp[i-1][0], nums1[i] * nums2[0])
        for j in range(1, n):
            dp[0][j] = max(dp[0][j-1], nums1[0] * nums2[j])
        
        # 填充dp表
        for i in range(1, m):
            for j in range(1, n):
                current = nums1[i] * nums2[j]
                dp[i][j] = max(
                    dp[i-1][j],                    # 不选nums1[i]
                    dp[i][j-1],                    # 不选nums2[j]
                    current,                       # 只选当前对
                    dp[i-1][j-1] + current        # 选当前对并连接
                )
        
        return dp[m-1][n-1]

public class Solution {
    public int MaxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.Length, n = nums2.Length;
        int[,] dp = new int[m, n];
        
        // 初始化第一行和第一列
        dp[0, 0] = nums1[0] * nums2[0];
        for (int i = 1; i < m; i++) {
            dp[i, 0] = Math.Max(dp[i-1, 0], nums1[i] * nums2[0]);
        }
        for (int j = 1; j < n; j++) {
            dp[0, j] = Math.Max(dp[0, j-1], nums1[0] * nums2[j]);
        }
        
        // 填充dp表
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int current = nums1[i] * nums2[j];
                dp[i, j] = Math.Max(Math.Max(
                    dp[i-1, j],                    // 不选nums1[i]
                    dp[i, j-1]),                   // 不选nums2[j]
                    Math.Max(
                    current,                       // 只选当前对
                    dp[i-1, j-1] + current));     // 选当前对并连接
            }
        }
        
        return dp[m-1, n-1];
    }
}

var maxDotProduct = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const dp = Array(m).fill().map(() => Array(n).fill(0));
    
    // 初始化第一行和第一列
    dp[0][0] = nums1[0] * nums2[0];
    for (let i = 1; i < m; i++) {
        dp[i][0] = Math.max(dp[i-1][0], nums1[i] * nums2[0]);
    }
    for (let j = 1; j < n; j++) {
        dp[0][j] = Math.max(dp[0][j-1], nums1[0] * nums2[j]);
    }
    
    // 填充dp表
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            const current = nums1[i] * nums2[j];
            dp[i][j] = Math.max(
                dp[i-1][j],                    // 不选nums1[i]
                dp[i][j-1],                    // 不选nums2[j]
                current,                       // 只选当前对
                dp[i-1][j-1] + current        // 选当前对并连接
            );
        }
    }
    
    return dp[m-1][n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(m × n)
空间复杂度O(m × n)

其中 m 和 n 分别是两个数组的长度。可以进一步优化空间复杂度到 O(min(m, n))，通过只保存前一行的状态。