Dynamic Programming Algorithm to Compute the Max Dot Product of

  • Time:2020-09-08 11:08:55
  • Class:Weblog
  • Read:38

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) —

Recommend:
How to Renew the Free SSL Certificates (Nginx Server)?
Design: How to Solve 503 Error of API when Resources are not ava
SteemJs Programming: What Happens on the Steem Blockchain in the
How to Set Up Your On-Call Duty when Your Steem Witness is Missi
Common Mistakes You Can Face With Trying to switch Your Hosting
Recursive Algorithm to Construct Binary Tree from Preorder and P
10 Common Reasons Why Your Blog Doesn’t Make Money
Trial Run During COVID: Tips for Transitioning to a Full-time Fr
Why You Need Multiple Streams of Income
What You Should Know About Being A Freelance Blogger
Share:Facebook Twitter
Comment list
Comment add