Dynamic Programming Algorithm to Compute the Max Dot Product of Two Subsequences

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

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:
Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:
Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:
Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:
1 <= nums1.length, nums2.length <= 500
-1000 <= nums1[i], nums2[i] <= 1000

Hint:
Use dynamic programming, define DP[i][j] as the maximum dot product of two subsequences starting in the position i of nums1 and position j of nums2.

Compute the Max Dot Product of Two Subsequences

We can use DFS (Depth First Search) to enumerate the possible subsequences combination of both, but the complexity is exponetial. The key to solve this problem is to re-use the intermediate results, via Dynamic Programming algorithm.

We use a two-dimensional array dp[i][j] to represent the maxium dot product of two subsequences that end with index i and j respectively for two subsequences. Then dp[i][j] should the maximum of these values: num1[i]*num2[j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1], dp[i-1][j-1]+nums1[i]*nums2[j].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

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

Complexity is quadric O(N^2) – and the space requirement is O(N^2) as well. The answer is dp[m-1][n-1] where m and n are the lengths of both sequences respectively.

–EOF (The Ultimate Computing & Technology Blog) —