LeetCode #1458. 两个子序列的最大点积

Source: Dev.to

Problem

给定两个数组 nums1 和 nums2，返回 nums1 与 nums2 中长度相同的非空子序列之间的最大点积。

数组的子序列是通过删除（或不删除）一些元素而得到的新数组，且不改变剩余元素的相对顺序。
例如，[2,3,5] 是 [1,2,3,4,5] 的子序列，而 [1,5,3] 不是。

Example 1

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: 从 nums1 中取子序列 [2,-2]，从 nums2 中取子序列 [3,-6]。它们的点积为 2*3 + (-2)*(-6) = 18。

Example 2

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: 从 nums1 中取子序列 [3]，从 nums2 中取子序列 [7]。它们的点积为 3*7 = 21。

Example 3

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: 从 nums1 中取子序列 [-1]，从 nums2 中取子序列 [1]。它们的点积为 -1。

Constraints

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

Discussion

该问题可以使用动态规划来求解，思路类似最长公共子序列（LCS）技术。
我们维护一个二维 DP 数组，其中 dp[i][j] 保存使用前缀 nums1[0..i] 和 nums2[0..j] 时的最大点积。
对于每一对 (i, j)，我们考虑以下四种情况：

1. 将之前的最佳子序列延伸，乘上 nums1[i] * nums2[j]。
2. 仅用 nums1[i] * nums2[j] 开启一个新子序列。
3. 跳过 nums1[i]（使用 dp[i‑1][j]）。
4. 跳过 nums2[j]（使用 dp[i][j‑1]）。

对第一行和第一列的特殊情况单独处理，以确保子序列非空。

Solution

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length][nums2.length];
        int firstRowMax = nums1[0] * nums2[0];
        dp[0][0] = firstRowMax;

        // Initialize first row
        for (int j = 1; j < nums2.length; j++) {
            int current = nums1[0] * nums2[j];
            firstRowMax = Math.max(firstRowMax, current);
            dp[0][j] = firstRowMax;
        }

        int answer = firstRowMax;

        // Fill the DP table
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int current = nums1[i] * nums2[j];
                if (j == 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], current);
                } else {
                    dp[i][j] = Math.max(
                        dp[i - 1][j - 1] + current,
                        Math.max(
                            current,
                            Math.max(dp[i - 1][j], dp[i][j - 1])
                        )
                    );
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        return answer;
    }
}