{"id":6825,"date":"2020-05-24T12:59:09","date_gmt":"2020-05-24T19:59:09","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6825"},"modified":"2020-05-24T13:32:41","modified_gmt":"2020-05-24T20:32:41","slug":"leetcode-1458-max-dot-product-of-two-subsequences","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1458-max-dot-product-of-two-subsequences\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1458. Max Dot Product of Two Subsequences"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1458. Max Dot Product of Two Subsequences - \u5237\u9898\u627e\u5de5\u4f5c EP330\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/Zj871uqXadE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given two arrays&nbsp;<code>nums1<\/code>&nbsp;and&nbsp;<code>nums2<\/code>.<\/p>\n\n\n\n<p>Return the maximum dot product&nbsp;between&nbsp;<strong>non-empty<\/strong>&nbsp;subsequences of nums1 and nums2 with the same length.<\/p>\n\n\n\n<p>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,&nbsp;<code>[2,3,5]<\/code>&nbsp;is a subsequence of&nbsp;<code>[1,2,3,4,5]<\/code>&nbsp;while&nbsp;<code>[1,5,3]<\/code>&nbsp;is not).<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums1 = [2,1,-2,5], nums2 = [3,0,-6]\n<strong>Output:<\/strong> 18\n<strong>Explanation:<\/strong> Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.\nTheir dot product is (2*3 + (-2)*(-6)) = 18.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums1 = [3,-2], nums2 = [2,-6,7]\n<strong>Output:<\/strong> 21\n<strong>Explanation:<\/strong> Take subsequence [3] from nums1 and subsequence [7] from nums2.\nTheir dot product is (3*7) = 21.<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums1 = [-1,-1], nums2 = [1,1]\n<strong>Output:<\/strong> -1\n<strong>Explanation: <\/strong>Take subsequence [-1] from nums1 and subsequence [1] from nums2.\nTheir dot product is -1.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums1.length, nums2.length &lt;= 500<\/code><\/li><li><code>-1000 &lt;= nums1[i], nums2[i] &lt;= 1000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1458-ep330.png\" alt=\"\" class=\"wp-image-6828\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1458-ep330.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1458-ep330-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/05\/1458-ep330-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[i][j] := max product of nums1[0~i], nums2[0~j].<\/p>\n\n\n\n<p>dp[i][j] = max(dp[i-1][j], dp[i][j -1], max(0, dp[i-1][j-1]) + nums1[i]*nums2[j])<\/p>\n\n\n\n<p>Time complexity: O(n1*n2)<br>Space complexity: O(n1*n2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {\n    const int n1 = nums1.size();\n    const int n2 = nums2.size();\n    \/\/ dp[i][j] = max dot product of two subsequences \n    \/\/ of nums1[0:i] and nums2[0:j]\n    vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN \/ 2));\n        \n    for (int i = 1; i <= n1; ++i)\n      for (int j = 1; j <= n2; ++j)\n        dp[i][j] = max({\n          dp[i - 1][j],\n          dp[i][j - 1],\n          max(0, dp[i - 1][j - 1]) + nums1[i - 1] * nums2[j - 1]\n        });\n    return dp[n1][n2];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {\n    const int n1 = nums1.size();\n    const int n2 = nums2.size();\n    \/\/ dp[i][j] = max dot product of two subsequences \n    \/\/ of nums1[0~i] and nums2[0~j]\n    vector<vector<int>> dp(n1, vector<int>(n2));\n        \n    for (int i = 0; i < n1; ++i)\n      for (int j = 0; j < n2; ++j) {\n        dp[i][j] = nums1[i] * nums2[j];\n        if (i > 0 && j > 0) dp[i][j] += max(0, dp[i - 1][j - 1]);\n        if (i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j]);\n        if (j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1]);     \n      }\n    return dp.back().back();\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two arrays&nbsp;nums1&nbsp;and&nbsp;nums2. Return the maximum dot product&nbsp;between&nbsp;non-empty&nbsp;subsequences of nums1 and nums2 with the same length. A subsequence of a array is a new array&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,229],"class_list":["post-6825","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-subsequence","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6825","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6825"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6825\/revisions"}],"predecessor-version":[{"id":6829,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6825\/revisions\/6829"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6825"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6825"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6825"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}