Leetcode 1458. Max Dot Product of Two Subsequences

Problem explanation

Given two lists of integers nums1 and nums2, you have to find the maximum dot product between non-empty subsequences of nums1 and nums2 of the same length. A subsequence of list is a new list which is formed from the original list by deleting some (can be none) of the integers without disturbing the relative positions of the remaining integers.

For example, given nums1 = [2,1,-2,5] and nums2 = [3,0,-6], the maximum dot product between two subsequences is 18. The two subsequences taken are [2,-2] from nums1 and [3,-6] from nums2.

Approach

The given problem can be solved using Dynamic Programming (DP). The DP table, dp[i][j], stores the maximum dot product of two subsequences nums1[0..i) and nums2[0..j). A subsequence ends in nums1[i-1] and nums2[j-1] if dp[i][j] is not less than dp[i-1][j-1].

Dynamic programming is used because there are overlapping subproblems. Each state i, j depends only on states with smaller i and j.

The main idea behind this approach is to calculate maximum possible dot product using all possible pairs of elements from both subarrays.

Let's elaborate this solution technique with the help of an example: for nums1 = [2,1,-2,5] and nums2 = [3,0,-6].

1. Initialize the DP table with smallest possible integer values.

2. Iterate over each element of nums1 (outer loop) and nums2 (inner loop).

3. Update dp[i+1][j+1] as maximum of dp[i][j+1], dp[i+1][j] and max(0, dp[i][j]) + nums1[i] * nums2[j].

4. The max dot product of two subsequences is stored in dp[m][n].

Python Solution

1
2python
3class Solution:
4    def maxDotProduct(self, nums1, nums2):
5        m, n = len(nums1), len(nums2)
6        dp = [[float('-inf')] * (n + 1) for _ in range(m + 1)]
7        for i in range(m):
8            for j in range(n):
9                dp[i + 1][j + 1] = max(dp[i][j] + nums1[i] * nums2[j], nums1[i] * nums2[j], dp[i + 1][j], dp[i][j + 1])
10        return dp[-1][-1]

Java Solution

1
2java
3class Solution {
4    public int maxDotProduct(int[] nums1, int[] nums2) {
5        int m = nums1.length, n = nums2.length;
6        int[][] dp = new int[m + 1][n + 1];
7        for (int i = 0; i <= m; i++)
8            Arrays.fill(dp[i], Integer.MIN_VALUE);
9        for (int i = 0; i < m; i++) 
10            for (int j = 0; j < n; j++)
11                dp[i + 1][j + 1] = Math.max(dp[i][j] + nums1[i] * nums2[j], Math.max(nums1[i] * nums2[j], Math.max(dp[i + 1][j], dp[i][j + 1])));
12        return dp[m][n];
13    }
14}

JavaScript Solution

1
2javascript
3var maxDotProduct = function(nums1, nums2) {
4    let m = nums1.length, n = nums2.length;
5    let dp = Array.from({length: m + 1}, () => Array(n + 1).fill(Number.MIN_SAFE_INTEGER));
6    for(let i = 0; i < m; i++) {
7        for(let j = 0; j < n; j++) {
8            dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j], Math.max(0, dp[i][j]) + nums1[i] * nums2[j]);
9        }
10    }
11    return dp[m][n];
12};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
6        int m = nums1.size(), n = nums2.size();
7        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
8        for(int i = 0; i < m; i++) {
9            for(int j = 0; j < n; j++) {
10                dp[i + 1][j + 1] = max({dp[i][j] + nums1[i] * nums2[j], nums1[i] * nums2[j], dp[i + 1][j], dp[i][j + 1]});
11            }
12        }
13        return dp[m][n];
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxDotProduct(int[] nums1, int[] nums2) {
5        int m = nums1.Length, n = nums2.Length;
6        int[,] dp = new int[m + 1, n + 1];
7        for(int i = 0; i <= m; i++)
8            for(int j = 0; j <= n; j++)
9                dp[i, j] = int.MinValue;
10        for(int i = 0; i < m; i++)
11            for(int j = 0; j < n; j++)
12                dp[i + 1, j + 1] = Math.Max(dp[i, j] + nums1[i] * nums2[j], Math.Max(nums1[i] * nums2[j], Math.Max(dp[i + 1, j], dp[i, j + 1])));
13        return dp[m, n];
14    }
15}

These solutions have a time complexity of O(mn), where m and n are the sizes of the given arrays. This is due to the nested loop iterating over every possible pair. The space complexity is also O(mn) as we are storing the result for the entire DP table.

Each approach above initially fills the DP table with the minimum integer value possible, indicating an invalid or not-yet-calculated state. During each iteration, it calculates the max dot product that includes current pair of elements, and also keeps track of the max dot product that doesn't include the current pair. In this way, the algorithm ensures it has calculated the maximum dot product up to the current pair, whether that pair is included in the product or not.

The final result is then found in the bottom-right cell of the DP table (dp[m][n]), which represents the max dot product of the entire sequences.

There are also some points to be noted:

1. Each language has a way to initialize a 2D array. For example, list comprehension is used in Python, Arrays.fill() in Java, Array.from() in JavaScript, and vector initialization in C++.
2. Identifying the maximum amongst a set of values: Python and JavaScript provide a max function which can take in any number of arguments. Java has Math.max() function but it only takes two arguments so it is used multiple times to get the maximum amongst multiple values. In C++, an initializer list is used with the max function.

The logic and approach remain the same, it's just the difference of syntax and built-in functions provided by each language.