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.
nums1 and nums2.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.
Example 3
Input
nums1 = [1,2], nums2 = [3,4]
Output
11
Explanation
Take both arrays entirely: 13 + 24 = 11.
Premium problem context
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.