{"id":2986,"date":"2018-07-03T21:49:04","date_gmt":"2018-07-04T04:49:04","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2986"},"modified":"2018-07-04T08:47:30","modified_gmt":"2018-07-04T15:47:30","slug":"leetcode-410-split-array-largest-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-410-split-array-largest-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 410. Split Array Largest Sum"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 410. Split Array Largest Sum - \u5237\u9898\u627e\u5de5\u4f5c EP203\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/_k-Jb4b7b_0?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><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Given an array which consists of non-negative integers and an integer\u00a0<i>m<\/i>, you can split the array into\u00a0<i>m<\/i>\u00a0non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these\u00a0<i>m<\/i>\u00a0subarrays.<\/p>\n<p><b>Note:<\/b><br \/>\nIf\u00a0<i>n<\/i>\u00a0is the length of array, assume the following constraints are satisfied:<\/p>\n<ul>\n<li>1 \u2264\u00a0<i>n<\/i>\u00a0\u2264 1000<\/li>\n<li>1 \u2264\u00a0<i>m<\/i>\u00a0\u2264 min(50,\u00a0<i>n<\/i>)<\/li>\n<\/ul>\n<p><b>Examples:<\/b><\/p>\n<pre class=\"crayon:false\">Input:\r\n<b>nums<\/b> = [7,2,5,10,8]\r\n<b>m<\/b> = 2\r\n\r\nOutput:\r\n18\r\n\r\nExplanation:\r\nThere are four ways to split <b>nums<\/b> into two subarrays.\r\nThe best way is to split it into <b>[7,2,5]<\/b> and <b>[10,8]<\/b>,\r\nwhere the largest sum among the two subarrays is only 18.\r\n<\/pre>\n<h1>\u00a0<img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2997\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2996\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2999\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/07\/410-ep203-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>Time complexity: O(n^2*m)<\/p>\n<p>Space complexity: O(n*m)<\/p>\n<p>C++ \/ Recursion + Memorization<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 111 ms\r\nclass Solution {\r\npublic:\r\n  int splitArray(vector&lt;int&gt;&amp; nums, int m) {\r\n    const int n = nums.size();\r\n    sums_ = vector&lt;int&gt;(n);\r\n    mem_ = vector&lt;vector&lt;int&gt;&gt;(n, vector&lt;int&gt;(m + 1, INT_MAX));\r\n    sums_[0] = nums[0];\r\n    for (int i = 1; i &lt; n; ++i)\r\n      sums_[i] = sums_[i - 1] + nums[i];\r\n    return splitArray(nums, n - 1, m);\r\n  }\r\nprivate:\r\n  vector&lt;vector&lt;int&gt;&gt; mem_;\r\n  vector&lt;int&gt; sums_;\r\n  \r\n  \/\/ min of largest sum of spliting nums[0] ~ nums[k] into m groups\r\n  int splitArray(const vector&lt;int&gt;&amp; nums, int k, int m) {\r\n    if (m == 1) return sums_[k];\r\n    if (m &gt; k + 1) return INT_MAX;    \r\n    if (mem_[k][m] != INT_MAX) return mem_[k][m];\r\n    int ans = INT_MAX;\r\n    for (int i = 0; i &lt; k; ++i)\r\n      ans = min(ans, max(splitArray(nums, i, m - 1), sums_[k] - sums_[i]));    \r\n    return mem_[k][m] = ans;\r\n  }\r\n};<\/pre>\n<p>C++ \/ DP<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 90 ms\r\nclass Solution {\r\npublic:\r\n  int splitArray(vector&lt;int&gt;&amp; nums, int m) {\r\n    const int n = nums.size();\r\n    vector&lt;int&gt; sums(n);\r\n    \/\/ dp[i][j] := min of largest sum of splitting nums[0] ~ nums[j] into i groups.\r\n    vector&lt;vector&lt;int&gt;&gt; dp(m + 1, vector&lt;int&gt;(n, INT_MAX));\r\n    sums[0] = nums[0];\r\n    for (int i = 1; i &lt; n; ++i)\r\n      sums[i] = sums[i - 1] + nums[i];\r\n    for (int i = 0; i &lt; n; ++i)\r\n      dp[1][i] = sums[i];\r\n    \r\n    for (int i = 2; i &lt;= m; ++i)\r\n      for (int j = i - 1; j &lt; n; ++j)\r\n        for (int k = 0; k &lt; j; ++k)\r\n          dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sums[j] - sums[k]));\r\n    return dp[m][n - 1];\r\n  }  \r\n};<\/pre>\n<h1><strong>Solution: Binary Search<\/strong><\/h1>\n<p>Time complexity: O(log(sum(nums))*n)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 3 ms\r\nclass Solution {\r\npublic:\r\n  int splitArray(vector&lt;int&gt;&amp; nums, int m) {\r\n    long l = *max_element(begin(nums), end(nums));\r\n    long r = accumulate(begin(nums), end(nums), 0L) + 1;\r\n    while (l &lt; r) {\r\n      long limit = (r - l) \/ 2 + l;\r\n      if (min_groups(nums, limit) &gt; m) \r\n        l = limit + 1;\r\n      else\r\n        r = limit;\r\n    }\r\n    return l;\r\n  }\r\nprivate:\r\n  int min_groups(const vector&lt;int&gt;&amp; nums, long limit) {\r\n    long sum = 0;\r\n    int groups = 1;\r\n    for (int num : nums) {\r\n      if (sum + num &gt; limit) {\r\n        sum = num;\r\n        ++groups;\r\n      } else {\r\n        sum += num;\r\n      }\r\n    }    \r\n    return groups;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given an array which consists of non-negative integers and an integer\u00a0m, you can split the array into\u00a0m\u00a0non-empty continuous subarrays. Write an algorithm to minimize&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,46],"tags":[18,316,217,317,41,62],"class_list":["post-2986","post","type-post","status-publish","format-standard","hentry","category-array","category-dynamic-programming","tag-dp","tag-groups","tag-hard","tag-largest","tag-subarray","tag-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2986","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=2986"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2986\/revisions"}],"predecessor-version":[{"id":3000,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2986\/revisions\/3000"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2986"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2986"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}