1458. Max Dot Product of Two Subsequences¶
题目信息¶
- 题号:
1458
- 难度:
Hard
- 主题:
动态规划、子序列、点积
- 原题:
- 重点:
从两个数组分别选择长度相同且非空的子序列,保持各自顺序,最大化对应元素乘积之和
题目重述¶
给定整数数组 nums1 和 nums2。分别从两个数组中选择一个非空子序列,要求两个子序列长度相同。
把两个子序列对应位置元素相乘并求和,得到点积。请返回所有合法选择中的最大点积。
1 <= nums1.length, nums2.length <= 500,-1000 <= nums1[i], nums2[i] <= 1000。
自建示例¶
多个对应项可以共同提高点积:
输入:nums1 = [2,-1], nums2 = [3,-2]
输出:8
解释:选择两个完整数组,点积为 2 * 3 + (-1) * (-2) = 8。
所有乘积为负时仍必须选择非空子序列:
输入:nums1 = [-1,-2], nums2 = [3,4]
输出:-3
解释:选择 -1 和 3 得到 -3,是所有非空方案中的最大值。