hardDynamic Programming 2DAI-applied~40 min
Maximum Dot Product of Two Aligned Subsequences
Two sequences of signed embedding coordinates are given. Pick an equal-length, order-preserving subsequence from each and align them so the sum of paired products (the dot product) is maximized. At least one pair must be chosen.
Problem
Given two integer arrays nums1 and nums2, choose non-empty subsequences of equal length from each (preserving order) and return the maximum dot product of the chosen aligned subsequences.
Input
Two integer arrays nums1 and nums2.
Output
An integer: the maximum achievable dot product.
Constraints
- 1 <= nums1.length, nums2.length <= 500
- -1000 <= values <= 1000
- At least one pair must be selected.
Examples
Example 1
Input
nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output
18
Pair 2 with 3 and -2 with -6: 6 + 12 = 18.
Example 2
Input
nums1 = [-1,-1], nums2 = [1,1]
Output
-1
Every product is negative; the best single pair is -1.