Find the maximum dot product obtainable by choosing two non-empty subsequences of equal length from two arrays.
Given two integer arrays, choose a non-empty subsequence from each array such that both subsequences have the same length. Pair the chosen elements in order and compute their dot product. Your task is to return the maximum possible dot product over all valid choices.
A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.
Because all pairs may produce a negative value, the optimal answer is not necessarily based on picking the longest subsequences or on keeping only positive numbers.
Input Format
- Two integer arrays
nums1andnums2. - Elements may be positive, negative, or zero.
- You must choose two non-empty subsequences of equal length.
Output Format
- Return a single integer: the maximum dot product of any valid pair of subsequences.
Constraints
- Both subsequences must be non-empty.
- The chosen subsequences must have the same length.
- The relative order of elements in each array must be preserved.
- Arrays may contain negative values, so the result may be negative.
Example 1
Input
nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output
18
Explanation
One optimal choice is subsequences [2,5] and [3,0]. Their dot product is 23 + 50 = 6. A better choice is [2,1,5] and [3,0,-6], giving 23 + 10 + 5*(-6) = -24, so not good. The maximum is achieved by [2,5] and [3,-6]? That is not valid because order must be preserved and lengths must match across chosen subsequences. The optimal valid pairing is [2,1,5] with [3,0,-6] under a different alignment in the DP formulation, yielding 18.
Example 2
Input
nums1 = [-1,-1], nums2 = [1,1]
Output
-1
Explanation
The best valid choice is to take one element from each array: (-1) * 1 = -1. Taking more pairs would only make the value smaller.
Show 1 more example
Example 3
Input
nums1 = [1,2], nums2 = [3,4]
Output
11
Explanation
Take both arrays entirely: 13 + 24 = 11.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.