Max Dot Product of Two Subsequences

Problem Description

Given two arrays nums1 and nums2, return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

Key Insights

• A subsequence allows for elements to be chosen from the arrays while maintaining their relative order.
• The dot product is calculated as the sum of the products of corresponding elements from two sequences.
• Dynamic programming is a suitable approach to solve this problem due to the overlapping subproblems and optimal substructure properties.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the lengths of nums1 and nums2 respectively.
Space Complexity: O(m * n) for the DP table.

Solution

The problem can be solved using dynamic programming. We will create a 2D DP table where dp[i][j] represents the maximum dot product of subsequences ending at indices i-1 in nums1 and j-1 in nums2.

1. Initialize a DP table of size (m+1) x (n+1) with values set to negative infinity to account for negative products.
2. Iterate through each element of nums1 and nums2.
3. For each pair of indices (i, j), compute the maximum dot product by considering:
   • The case of including both nums1[i-1] and nums2[j-1] in the product.
   • The case of skipping one of the elements.
4. Return the maximum value from the DP table that corresponds to non-empty subsequences.

Code Solutions