1458. Max Dot Product of Two Subsequences

题目信息

题号:

1458

难度:

Hard

主题:

动态规划、子序列、点积

原题:

LeetCode 1458

重点:

从两个数组分别选择长度相同且非空的子序列,保持各自顺序,最大化对应元素乘积之和

题目重述

给定整数数组 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,是所有非空方案中的最大值。