LeetCode 1458. 两个子序列的最大点积
题目描述
题意分析
从两个数组中分别选择一个子序列，使两条子序列长度相同且都非空，再把对应位置的元素两两相乘后求和，要求这个点积最大。
子序列可以跳过元素，但必须保留各自原有的相对顺序，不能排序后重新配对。所选元素不要求数值相等，两边的原下标也不要求相同。乘积和可能为负，即使所有可选结果都为负，也必须选至少一对，不能用空选择得到零。
解法：DP
核心思路
[!blue]
定义
dp[i][j]为在nums1的前i个元素和nums2的前j个元素中，选择等长非空子序列所能得到的最大点积。两个前缀长度不同并不影响选择，因为可以在任一侧跳过元素；真正需要一致的是已经选择的配对数量。考虑两个前缀的最后元素。如果两者都被选中，它们必然是各自所选子序列的最后一个元素，也就必须互相配对。当前贡献为
val = nums1[i - 1] × nums2[j - 1]，前面的配对只能来自两个更短前缀，因此可以接上dp[i - 1][j - 1]。如果旧配对总收益为负，保留它反而会降低答案，可以直接从当前这一对重新开始。于是当前配对候选统一写成
val + max(0, dp[i - 1][j - 1])。这里的零只表示不接旧前缀，当前这一对始终已经被选中，因此仍然保证非空。如果两个当前元素没有同时选中，那么至少有一侧的当前元素被跳过，分别继承
dp[i - 1][j]或dp[i][j - 1]。这两类与当前配对一起覆盖全部可能选择，取最大值即可；两侧都跳过的情况也已经包含在继承状态中。任意一侧前缀为空时，不可能形成非空等长选择，边界必须设为足够小的负值，而不是零。这样全负结果不会被非法空答案压过。按前缀长度递增填表后，完整两个前缀的状态已经包含所有合法选择，直接返回即可。
解题步骤
- 创建
(n + 1) × (m + 1)的状态表，初始化为表示不可达的负无穷哨兵。- 从两个前缀长度一开始递增计算，求当前两个末尾元素的乘积
val。- 计算当前配对候选：只选这一对，或把它接到正收益的旧配对后面。
- 再比较跳过第一数组当前元素、跳过第二数组当前元素两种继承状态。
- 将三种候选最大值写入当前状态，最终返回
dp[n][m]。
代码实现
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)。每个双前缀状态只做固定次数的乘法、加法与比较。- 空间复杂度：
O(nm)，保存完整的二维最大点积表。
关键点总结
[!green]
- 双前缀状态保留两侧顺序，选一对时两个前缀同时缩小，跳过时只缩小一侧。
- 当前配对可以单独作为新起点，负收益旧前缀无需强行保留。
- 空边界不可达与配对分支至少选一对，共同保证最终答案非空。
- 配对贡献取决于乘积，不要求元素相等，也不需要固定相同原下标。
易错点总结
[!yellow]
- 把空前缀初始化为零：全负结果会被非法的空选择替代。
- 当前乘积总是加上旧状态：会受负收益或不可达状态拖累，必须允许从当前一对重新开始。
- 把
max(0, ...)理解为允许最终空答案：当前配对的乘积仍然加入，零只用于舍弃旧前缀。- 排序后配对：改变了元素相对顺序，已经不是原数组的子序列。
- 只允许两边同下标配对或仅一侧跳过：会漏掉合法的保序交叉选择，需要独立推进两个前缀。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同样在两个序列前缀上选择匹配或跳过，本题匹配贡献是乘积且可能为负，必须保证结果非空。 |
| 1035. 不相交的线 | 中等 | 所选配对都要保持两侧下标顺序，本题不要求值相等，而是优化配对乘积总和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！