LeetCode 1458. 两个子序列的最大点积
目录
题目描述
题意分析
从
nums1里挑一个子序列、从nums2里挑一个子序列，要求两者长度相同且都非空，把它们按位相乘再求和，最大化这个和。
三个条件缺一不可。「子序列」意味着可以跳过元素但不能改变相对顺序，这是双序列 DP 的标准前提。「长度相同」意味着两边的选择必须配对——每选一个
nums1[i]，必须同时选一个nums2[j]与它相乘，不存在单边多选。「非空」是这道题真正的难点所在：如果允许空，答案永远可以取 0（什么都不选），题目就退化了。
「非空」这个约束会带来一个反直觉的情形：当
nums1全是正数、nums2全是负数时，任何配对的乘积都是负的，答案必然为负。此时最优解是只配一对——绝对值最小的正数乘绝对值最小的负数。这类用例是本题的主要 WA 来源，必须在设计初始值时就照顾到，而不是靠事后打补丁。
约束方面，两个数组长度都在 500 以内，元素绝对值不超过 500。$O(nm)$ 的二维表最多 25 万个状态，完全可行。单项乘积最大 $500 \times 500 = 250000$，累加最多 500 项，总和绝对值不超过 $1.25 \times 10^8$，
int装得下，不需要long——但用来表示「不可达」的负无穷哨兵必须选得既足够小又不会在加法中溢出。
边界：任一数组长度为 1 时，答案是它那个元素与另一数组中某个元素的最大乘积；两数组符号完全相反时答案必为负；符号混合时答案必然可以取到正值（总能找到一对同号的数）。
解法：DP
核心思路
暴力是枚举两边所有子序列再配对，指数级，不可行。转向 DP 的第一步是找出「最后一个决策」：考虑
nums1的第i个元素和nums2的第j个元素，它们要么被配成一对，要么至少有一个被丢弃。三个转移覆盖了所有合法方案；跳过分支之间可以重叠，但取最大值不受影响。
定义状态：
dp[i][j]表示只在前缀nums1[0..i-1]和nums2[0..j-1]中挑选、且两个子序列都非空时，能取到的最大点积。用i、j表示「前i个 / 前j个」而不是「下标i」，是为了让空前缀自然对应到i = 0，省掉一堆越界判断。
转移分三种决策：
- 把
nums1[i-1]和nums2[j-1]配成一对。这一对的贡献是val = nums1[i-1] * nums2[j-1]，前面的部分可以选也可以不选——若dp[i-1][j-1]是正的就带上它，若是负的（或者是「前缀太短还凑不出非空解」的不可达状态）就干脆只要这一对。写成val + max(0, dp[i-1][j-1])。这个max(0, ...)是全题最精妙的一行：它同时完成了两件事——丢弃亏损的前缀，以及为「只配这一对」提供合法起点，从而在不写任何特判的情况下满足了「非空」约束。- 不要
nums1[i-1]，答案继承dp[i-1][j]。- 不要
nums2[j-1]，答案继承dp[i][j-1]。三者取最大即是
dp[i][j]。
初始化是本题的第二个关键点。
dp[0][j]和dp[i][0]全部设为负无穷，因为空前缀不可能凑出非空子序列，这些状态是不可达的，绝不能设为 0。若设成 0，决策 2、3 就会把「一个都不选」这个非法解偷偷带进来，nums1 = [-1]、nums2 = [1]会输出 0 而正确答案是 -1。
负无穷起到了双重作用：一方面它让不可达状态永远无法通过决策 2、3 被选中；另一方面
max(0, dp[i-1][j-1])里的 0 会把它挡住，使得决策 1 退化成「只取当前这一对」——这正是我们想要的语义。
不变量可以这样表述：填完
dp[i][j]时，它精确等于「在两个前缀里各选一个等长非空子序列」的最大点积；若这样的选法不存在（i或j为 0），它是负无穷。最终答案是dp[n][m]，因为题目允许使用整个数组作为可选范围。
解题步骤
- 开
(n+1) × (m+1)的表并全部填负无穷：包括第 0 行、第 0 列。哨兵取-10^9，它严格小于任何合法答案。当前转移先做max(0, dp[i-1][j-1])，不会把哨兵参与加法；即便以后改写转移，这个取值也留有足够的算术余量。- 双重循环
i从 1 到 n、j从 1 到 m：依赖的三个来源dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]在行序遍历下都已经算好，顺序合法。- 先算配对决策：
val = nums1[i-1] * nums2[j-1]，候选值是val + max(0, dp[i-1][j-1])。其中 0 只表示「从当前这一对重新开始」，并不是最终允许空选；跳过分支以负无穷为边界，才共同保证结果至少包含一对元素。- 再用两个跳过决策松弛：分别与
dp[i-1][j]、dp[i][j-1]取最大。注意它们可能是负无穷，取最大时自然被淘汰，不需要额外判断。- 返回
dp[n][m]。这个状态一定可达（n、m都至少为 1），不会是负无穷。
以
nums1 = [2, 1, -2, 5]、nums2 = [3, 0, -6]走一遍（n = 4，m = 3）。第 0 行第 0 列全是负无穷，记作-∞。
i = 1（
nums1[0] = 2）：
j = 1（nums2[0] = 3）：val = 6，配对候选6 + max(0, -∞) = 6；跳过候选都是-∞。dp[1][1] = 6。
j = 2（nums2[1] = 0）：val = 0，配对时看的是dp[0][1] = -∞，于是候选为0 + max(0, -∞) = 0；跳过候选dp[0][2] = -∞、dp[1][1] = 6。dp[1][2] = 6。
j = 3（-6）：val = -12，配对候选-12 + max(0, dp[0][2]) = -12；跳过候选dp[0][3] = -∞、dp[1][2] = 6。dp[1][3] = 6。
i = 2（
nums1[1] = 1）：
j = 1：val = 3，配对候选3 + max(0, dp[1][0]) = 3；跳过dp[1][1] = 6、dp[2][0] = -∞。dp[2][1] = 6。
j = 2：val = 0，配对候选0 + max(0, dp[1][1]) = 0 + 6 = 6；跳过dp[1][2] = 6、dp[2][1] = 6。dp[2][2] = 6。
j = 3：val = -6，配对候选-6 + max(0, dp[1][2]) = -6 + 6 = 0；跳过dp[1][3] = 6、dp[2][2] = 6。dp[2][3] = 6。
i = 3（
nums1[2] = -2）：
j = 1：val = -6，配对候选-6；跳过dp[2][1] = 6。dp[3][1] = 6。
j = 2：val = 0，配对候选0 + max(0, dp[2][1]) = 6；跳过均为 6。dp[3][2] = 6。
j = 3：val = 12，配对候选12 + max(0, dp[2][2]) = 12 + 6 = 18；跳过dp[2][3] = 6、dp[3][2] = 6。dp[3][3] = 18。
i = 4（
nums1[3] = 5）：
j = 1：val = 15，配对候选15 + max(0, dp[3][0]) = 15；跳过dp[3][1] = 6。dp[4][1] = 15。
j = 2：val = 0，配对候选0 + max(0, dp[3][1]) = 6；跳过dp[3][2] = 6、dp[4][1] = 15。dp[4][2] = 15。
j = 3：val = -30，配对候选-30 + max(0, dp[3][2]) = -24；跳过dp[3][3] = 18、dp[4][2] = 15。dp[4][3] = 18。
返回 18，对应选
nums1的[2, -2]与nums2的[3, -6]，点积2*3 + (-2)*(-6) = 6 + 12 = 18。
再用极端用例验证初始化：
nums1 = [-1]、nums2 = [1]。dp[1][1]的配对候选是-1 + max(0, dp[0][0]) = -1 + 0 = -1，两个跳过候选都是-∞，所以dp[1][1] = -1，正确。若把第 0 行第 0 列初始化成 0，跳过候选就是 0，答案会变成 0，直接判错。
代码实现
import java.util.Arrays;
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int[][] dp = new int[n + 1][m + 1];
// 空前缀凑不出非空子序列，必须是不可达而不是 0。
int negInf = -1_000_000_000;
for (int[] row : dp) {
Arrays.fill(row, negInf);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int val = nums1[i - 1] * nums2[j - 1];
// max(0, ...) 同时实现「丢弃亏损前缀」和「只配这一对」两种语义。
dp[i][j] = Math.max(dp[i][j], val + Math.max(0, dp[i - 1][j - 1]));
// 跳过 nums1[i-1] 或 nums2[j-1]；不可达来源是负无穷，会被自动淘汰。
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
}
func maxDotProduct(nums1 []int, nums2 []int) int {
n := len(nums1)
m := len(nums2)
// 空前缀凑不出非空子序列，必须是不可达而不是 0。
negInf := -1_000_000_000
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = negInf
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
val := nums1[i-1] * nums2[j-1]
// 前缀为正才带上，否则只配这一对，等价于 val + max(0, dp[i-1][j-1])。
best := val
if dp[i-1][j-1] > 0 {
best = val + dp[i-1][j-1]
}
dp[i][j] = maxInt(dp[i][j], best)
// 跳过 nums1[i-1] 或 nums2[j-1]；不可达来源是负无穷，会被自动淘汰。
dp[i][j] = maxInt(dp[i][j], dp[i-1][j])
dp[i][j] = maxInt(dp[i][j], dp[i][j-1])
}
}
return dp[n][m]
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(nm)$。每个状态
dp[i][j]只被计算一次，计算过程是一次乘法加三次取最大，全是常数操作。n、m上限 500，状态数 25 万，运行时间可以忽略。- 空间复杂度：$O(nm)$，用于保存二维状态表；返回值只占常数空间。
关键点总结
max(0, dp[i-1][j-1])是本题的题眼。它用一行代码同时表达了「前缀亏损就丢掉」和「允许只取当前这一对」，从而在没有任何特判的情况下满足了「子序列非空」的约束。看到「必须非空」的最优化题，先想能不能用这种「0 作为可选起点」的写法。- 不可达状态必须用负无穷，不能用 0。这是「非空约束」的另一半实现。全负配全正的用例（如
nums1 = [-1]、nums2 = [1]）是专门用来打这个错误的，面试时应主动举出来说明自己考虑到了。- 负无穷必须严格小于任何合法答案，否则全为负贡献时，非法的空前缀状态可能反而更大并被继承。
- 双序列 DP 的通用骨架：状态是「两个前缀」，转移是「配对 / 跳过左 / 跳过右」三选一。1143、718、72、1035 全都是这套骨架的变体，差别只在配对的收益函数和是否允许跳过。
- 状态用「前
i个」而不是「下标i」，让空前缀落在 0 处，边界处理会干净很多。
易错点总结
- 把
dp[0][*]和dp[*][0]初始化为 0：nums1 = [-1]、nums2 = [1]会通过「跳过」决策继承到 0，输出 0，而正确答案是 -1。这是本题最经典的错误。- 漏掉
max(0, ...)，直接写val + dp[i-1][j-1]：nums1 = [-1]、nums2 = [1]时唯一配对会被负无穷前缀拖成不可达，算法无法从任何位置开始一个非空方案；正确答案是 -1。- 负无穷取值不够小：若用
-1，nums1 = [-5,-3]、nums2 = [2,4]的所有合法点积都不大于 -6，跳过分支却会继承非法的 -1 并把它当答案；正确答案是 -6。- 认为答案一定非负而把最终结果与 0 取最大：
nums1 = [-5, -3]、nums2 = [2, 4]的正确答案是 -6（选 -3 和 2），强行与 0 取最大会输出 0。- 下标偏移写成
nums1[i] * nums2[j]：i最大取到n，直接越界；即使不越界，每个状态配对的也是错位的元素，答案全错。- 误以为子序列可以重排：若先给两个数组排序再配对，
nums1 = [2, 1, -2, 5]、nums2 = [3, 0, -6]会得到错误的更优值，而题目要求保持相对顺序。- 允许两边长度不等（例如让一边可以「空配」）：
nums1 = [1]、nums2 = [-1, -1]会因为多配一项而算出更小的值，或者因为「不选」被当作合法解而返回 0。- 滚动数组优化时忘记缓存
dp[i-1][j-1]：在同一行内先写dp[j]再用dp[j-1]时，左上角的旧值已被本行覆盖，转移用到的是dp[i][j-1]而不是dp[i-1][j-1]，结果偏大。- 只用
dp[i-1][j-1]转移而不写两个跳过分支：等价于强制配对相同位置，nums1 = [1, 5]、nums2 = [5]会漏掉「跳过nums1[0]」的最优解 25，输出 5。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同一骨架但配对收益恒为 1 且要求字符相等，允许空解所以初始化用 0 |
| 1035. 不相交的线 | 中等 | 几何描述下的 LCS，重点在把「连线不交叉」翻译成「保持相对顺序」 |
| 718. 最长重复子数组 | 中等 | 要求连续，一旦失配必须归零，不能继承跳过分支 |
| 72. 编辑距离 | 中等 | 求最小代价，三种决策变成增删改，边界填的是前缀长度而非负无穷 |
| 583. 两个字符串的删除操作 | 中等 | 只允许删除的编辑距离，可直接由 LCS 长度反推，考察问题等价转化 |
| 115. 不同的子序列 | 困难 | 双序列计数而非求最值，转移用加法且要注意方案数溢出 |