Max Dot Product of Two Subsequences
Given two arrays nums1 and nums2.
Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.
A subsequence of an array is a new array formed from the original array by deleting some elements, possibly none, without disturbing the relative positions of the remaining elements. For example, [2, 3, 5] is a subsequence of [1, 2, 3, 4, 5], while [1, 5, 3] is not.
Example 1
Input
nums1 = [2,1,-2,5], nums2 = [3,0,-6]Output
18Take subsequence [2, -2] from nums1 and subsequence [3, -6] from nums2; their dot product is 2 * 3 + (-2) * (-6) = 18.
Example 2
Input
nums1 = [3,-2], nums2 = [2,-6,7]Output
21Take subsequence [3] from nums1 and subsequence [7] from nums2; their dot product is 3 * 7 = 21.
Constraints
- 1 <= nums1.length, nums2.length <= 500
- -1000 <= nums1[i], nums2[i] <= 1000