What is the core pattern in Max Dot Product of Two Subsequences?

The core pattern is state transition dynamic programming on two indices. Each state decides whether to pair the current elements, skip in nums1, or skip in nums2, while enforcing that at least one pair is chosen.

Why is this problem not solved by a standard subsequence DP that uses 0 as the base answer?

Because 0 represents taking nothing, which is illegal here. If every valid pairing is negative, a 0-initialized DP will incorrectly prefer the empty choice over the required non-empty subsequences.

Why do we compare the current product alone against extending the diagonal DP state?

Sometimes the best answer starts at the current pair, and extending a previous subsequence would only make it worse. Comparing product alone with product plus the diagonal state captures both starting fresh and continuing an existing matched subsequence.

Can Max Dot Product of Two Subsequences be solved in O(mn)?

Yes. There are m times n index pairs, and each state does constant work from nearby states, so the DP runs in O(mn) time.

What edge case most often breaks correct solutions for LeetCode 1458?

The biggest failure mode is all-negative or sign-opposed inputs where the best valid result is still negative. Any solution that silently allows an empty subsequence will fail that case.

#1458

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

两个子序列的最大点积

给你两个数组 nums1 和 nums2 。请你返回 nums1 和 nums2 中两个长度相同的非空子序列的最大点积。数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说， [2,3,5] 是 [1,2,3,4,5] 的一个子…

数组动态规划

题目描述

给你两个数组 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

点积：

定义 a = [a₁, a₂,…, a_n] 和 b = [b₁, b₂,…, b_n] 的点积为：



这里的 Σ 指示总和符号。

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示 $\textit{nums1}$ 的前 $i$ 个元素和 $\textit{nums2}$ 的前 $j$ 个元素构成的两个子序列的最大点积。初始时 $f[i][j] = -\infty$ 。

对于 $f[i][j]$ ，我们有以下几种情况：

不选 $\textit{nums1}[i-1]$ 或者不选 $\textit{nums2}[j-1]$ ，即 $f[i][j] = \max(f[i-1][j], f[i][j-1])$ ；
选 $\textit{nums1}[i-1]$ 和 $\textit{nums2}[j-1]$ ，即 $f[i][j] = \max(f[i][j], \max(0, f[i-1][j-1]) + \textit{nums1}[i-1] \times \textit{nums2}[j-1])$ 。

最终答案即为 $f[m][n]$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是数组 $\textit{nums1}$ 和 $\textit{nums2}$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        f = [[-inf] * (n + 1) for _ in range(m + 1)]
        for i, x in enumerate(nums1, 1):
            for j, y in enumerate(nums2, 1):
                v = x * y
                f[i][j] = max(f[i - 1][j], f[i][j - 1], max(0, f[i - 1][j - 1]) + v)
        return f[m][n]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They ask how your DP prevents choosing empty subsequences when every product is negative.
question_mark
They push on why the transition must compare taking the current pair alone versus extending dp[i+1][j+1].
question_mark
They ask whether the same recurrence still works when zeros appear and when one strong pair beats every longer subsequence.

warning

常见陷阱

外企场景

error
Initializing DP with 0 and accidentally allowing an empty subsequence to beat valid negative answers.
error
Using a longest-common-subsequence style transition without the take-current-pair-alone case, which misses single-pair optima.
error
Forgetting that skipping is allowed independently in either array, so the DP must compare skip nums1 and skip nums2 at every state.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual subsequences that produce the maximum dot product instead of only the score.
arrow_right_alt
Restrict the solution to subsequences of exactly k matched pairs, which adds a length dimension to the DP.
arrow_right_alt
Change the objective to minimum dot product, which flips the transition logic and changes which negative states are desirable.

help

常见问题

外企场景

继续练习

#1463 摘樱桃 II #1449 数位成本和为目标值的最大数字 #1467 两个盒子中球的颜色数相同的概率