Solution Explanation: Max Dot Product of Two Subsequences

This problem asks to find the maximum dot product between non-empty subsequences of equal length from two input arrays, nums1 and nums2. A brute-force approach would be computationally expensive. The optimal solution uses dynamic programming.

Approach: Dynamic Programming

The dynamic programming approach builds a solution bottom-up. We create a 2D array, dp, where dp[i][j] represents the maximum dot product achievable using subsequences from the first i elements of nums1 and the first j elements of nums2.

Base Case: dp[0][j] = dp[i][0] = -∞ (no subsequences possible with zero elements).

Recursive Relation: For dp[i][j], we consider two possibilities:

1. Exclude nums1[i-1] or nums2[j-1]: The maximum dot product is the maximum of dp[i-1][j] and dp[i][j-1].

2. Include nums1[i-1] and nums2[j-1]: The dot product increases by nums1[i-1] * nums2[j-1]. However, we need to consider if including this product makes the overall dot product negative. We take max(0, dp[i-1][j-1]) before adding the product, ensuring that a negative dot product from previous elements doesn't ruin the overall maximum.

Therefore, the recursive relation is:

dp[i][j] = max(dp[i-1][j], dp[i][j-1], max(0, dp[i-1][j-1]) + nums1[i-1] * nums2[j-1])

The final answer is dp[m][n], where m and n are the lengths of nums1 and nums2, respectively.

Time and Space Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the lengths of the input arrays. We iterate through the dp array once.

• Space Complexity: O(mn) to store the dp array. We can optimize this to O(min(m,n)) using techniques like rolling arrays (only keeping the last row/column), but for simplicity, the provided solutions use O(mn) space.

Code in Different Languages

The following code implements the dynamic programming solution in various programming languages. The logic remains the same across all implementations. Note the use of a large negative value (-inf or Integer.MIN_VALUE) to initialize the dp array, representing an invalid or unreachable state.

Python

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[-float('inf')] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1])
        return dp[m][n]
 

Java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp) Arrays.fill(row, Integer.MIN_VALUE);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = Math.max(dp[i][j], Math.max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1]);
            }
        }
        return dp[m][n];
    }
}

C++

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, LLONG_MIN));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = max(dp[i][j], max(0LL, dp[i - 1][j - 1]) + (long long)nums1[i - 1] * nums2[j - 1]);
            }
        }
        return (int)dp[m][n];
    }
};

Javascript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDotProduct = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(-Infinity));
 
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1], Math.max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1]);
        }
    }
    return dp[m][n];
};

The other languages (Go, TypeScript, Rust) would follow a very similar pattern, implementing the same dynamic programming logic. The key is the initialization of the dp array with a large negative value and the core recursive relation to build the solution efficiently.