{"id":7197,"date":"2020-08-02T12:52:45","date_gmt":"2020-08-02T19:52:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7197"},"modified":"2020-08-02T13:19:56","modified_gmt":"2020-08-02T20:19:56","slug":"leetcode-1537-get-the-maximum-score","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-1537-get-the-maximum-score\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1537. Get the Maximum Score"},"content":{"rendered":"\n<p>You are given two&nbsp;<strong>sorted<\/strong>&nbsp;arrays of distinct integers&nbsp;<code>nums1<\/code>&nbsp;and&nbsp;<code>nums2.<\/code><\/p>\n\n\n\n<p>A&nbsp;<strong>validpath<\/strong>&nbsp;is defined as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose&nbsp;array nums1 or nums2 to traverse (from index-0).<\/li><li>Traverse the current array from left to right.<\/li><li>If you are reading any value that is present in&nbsp;<code>nums1<\/code>&nbsp;and&nbsp;<code>nums2<\/code>&nbsp;you are allowed to change your path to the other array. (Only one repeated value is considered in the&nbsp;valid path).<\/li><\/ul>\n\n\n\n<p><em>Score<\/em>&nbsp;is defined as the sum of uniques values in a valid path.<\/p>\n\n\n\n<p>Return the maximum&nbsp;<em>score<\/em>&nbsp;you can obtain of all possible&nbsp;<strong>valid&nbsp;paths<\/strong>.<\/p>\n\n\n\n<p>Since the answer&nbsp;may be too large,&nbsp;return it modulo&nbsp;10^9 + 7.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/07\/16\/sample_1_1893.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]\n<strong>Output:<\/strong> 30\n<strong>Explanation:<\/strong>&nbsp;Valid paths:\n[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)\n[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)\nThe maximum is obtained with the path in green <strong>[2,4,6,8,10]<\/strong>.\n<\/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 = [1,3,5,7,9], nums2 = [3,5,100]\n<strong>Output:<\/strong> 109\n<strong>Explanation:<\/strong>&nbsp;Maximum sum is obtained with the path <strong>[1,3,5,100]<\/strong>.\n<\/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,2,3,4,5], nums2 = [6,7,8,9,10]\n<strong>Output:<\/strong> 40\n<strong>Explanation:<\/strong>&nbsp;There are no common elements between nums1 and nums2.\nMaximum sum is obtained with the path [6,7,8,9,10].\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]\n<strong>Output:<\/strong> 61\n<\/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 &lt;= 10^5<\/code><\/li><li><code>1 &lt;= nums2.length &lt;= 10^5<\/code><\/li><li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10^7<\/code><\/li><li><code>nums1<\/code>&nbsp;and&nbsp;<code>nums2<\/code>&nbsp;are strictly increasing.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Two Pointers + DP<\/strong><\/h2>\n\n\n\n<p>Since numbers are strictly increasing, we can always traverse the smaller one using two pointers. <br>Traversing ([2,4,5,8,10], [4,6,8,10])<br>will be like [2, 4\/4, 5, 6, 8, 10\/10]<br>It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.<br>dp1[i] := max path sum ends with nums1[i-1]<br>dp2[j] := max path sum ends with nums2[j-1]<br>if nums[i -1] == nums[j &#8211; 1]:<br>  dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]<br>  i += 1, j += 1<br>else if nums[i &#8211; 1] &lt; nums[j &#8211; 1]:<br>  dp[i] = dp[i-1] + nums[i -1]<br>  i += 1<br>else if nums[j &#8211; 1] &lt; nums[i &#8211; 1]:<br>  dp[j] = dp[j-1] + nums[j -1]<br>  j += 1<br>return max(dp1[-1], dp2[-1])<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n) -&gt; O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int maxSum(vector<int>& nums1, vector<int>& nums2) {\n    constexpr int kMod = 1e9 + 7;\n    const int n1 = nums1.size();\n    const int n2 = nums2.size();\n    vector<long> dp1(n1 + 1); \/\/ max path sum ends with nums1[i-1]\n    vector<long> dp2(n2 + 1); \/\/ max path sum ends with nums2[j-1]\n    int i = 0;\n    int j = 0;\n    while (i < n1 || j < n2) {\n      if (i < n1 &#038;&#038; j < n2 &#038;&#038; nums1[i] == nums2[j]) {\n        \/\/ Same, two choices, pick the larger one.\n        dp2[j + 1] = dp1[i + 1] = max(dp1[i], dp2[j]) + nums1[i];\n        ++i; ++j;\n      } else if (i < n1 &#038;&#038; (j == n2 || nums1[i] < nums2[j])) {\n        dp1[i + 1] = dp1[i] + nums1[i];\n        ++i;\n      } else if (j < n2 &#038;&#038; (i == n1 || nums2[j] < nums1[i])) {        \n        dp2[j + 1] = dp2[j] + nums2[j];\n        ++j;\n      }\n    }    \n    return max(dp1.back(), dp2.back()) % kMod;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {\n  public int maxSum(int[] nums1, int[] nums2) {\n    final int kMod = 1_000_000_007;\n    int n1 = nums1.length;\n    int n2 = nums2.length;\n    int i = 0;\n    int j = 0;\n    long a = 0;\n    long b = 0;\n    while (i < n1 || j < n2) {\n      if (i < n1 &#038;&#038; j < n2 &#038;&#038; nums1[i] == nums2[j]) {\n        a = b = Math.max(a, b) + nums1[i];\n        ++i;\n        ++j;\n      } else if (i < n1 &#038;&#038; (j == n2 || nums1[i] < nums2[j])) {\n        a += nums1[i++];        \n      } else {\n        b += nums2[j++];\n      }\n    }\n    return (int)(Math.max(a, b) % kMod);\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n    n1, n2 = len(nums1), len(nums2)\n    i, j = 0, 0\n    a, b = 0, 0\n    while i < n1 or j < n2:\n      if i < n1 and j < n2 and nums1[i] == nums2[j]:\n        a = b = max(a, b) + nums1[i]\n        i += 1\n        j += 1\n      elif i < n1 and (j == n2 or nums1[i] < nums2[j]):\n        a += nums1[i]\n        i += 1\n      else:\n        b += nums2[j]\n        j += 1\n    return max(a, b) % (10**9 + 7)        \n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given two&nbsp;sorted&nbsp;arrays of distinct integers&nbsp;nums1&nbsp;and&nbsp;nums2. A&nbsp;validpath&nbsp;is defined as follows: Choose&nbsp;array nums1 or nums2 to traverse (from index-0). Traverse the current array from left&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[18,217,640],"class_list":["post-7197","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-dp","tag-hard","tag-two-poiners","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7197","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=7197"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7197\/revisions"}],"predecessor-version":[{"id":7201,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7197\/revisions\/7201"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7197"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7197"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7197"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}