{"id":2449,"date":"2018-04-09T09:13:04","date_gmt":"2018-04-09T16:13:04","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2449"},"modified":"2018-09-03T21:59:35","modified_gmt":"2018-09-04T04:59:35","slug":"leetcode-813-largest-sum-of-averages","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-813-largest-sum-of-averages\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 813. Largest Sum of Averages"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 813. Largest Sum of Averages - \u5237\u9898\u627e\u5de5\u4f5c EP179\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/IPdShoUE9z8?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>\u9898\u76ee\u5927\u610f\uff1a\u628a\u4e00\u4e2a\u6570\u7ec4\u5206\u6210k\u4e2a\u6bb5\uff0c\u6c42\u6bcf\u6bb5\u5e73\u5747\u503c\u548c\u7684\u6700\u5927\u503c\u3002<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/largest-sum-of-averages\/description\/\">https:\/\/leetcode.com\/problems\/largest-sum-of-averages\/description\/<\/a><\/p>\n<p>We partition a row of numbers\u00a0<code>A<\/code>\u00a0into at most\u00a0<code>K<\/code>\u00a0adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?<\/p>\n<p>Note that our partition must use every number in A, and that scores are not necessarily integers.<\/p>\n<pre class=\"crayon:false\"><strong>Example:<\/strong>\r\n<strong>Input:<\/strong> \r\nA = [9,1,2,3,9]\r\nK = 3\r\n<strong>Output:<\/strong> 20\r\n<strong>Explanation:<\/strong> \r\nThe best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) \/ 3 + 9 = 20.\r\nWe could have also partitioned A into [9, 1], [2], [3, 9], for example.\r\nThat partition would lead to a score of 5 + 2 + 6 = 13, which is worse.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= A.length &lt;= 100<\/code>.<\/li>\n<li><code>1 &lt;= A[i] &lt;= 10000<\/code>.<\/li>\n<li><code>1 &lt;= K &lt;= A.length<\/code>.<\/li>\n<li>Answers within\u00a0<code>10^-6<\/code>\u00a0of the correct answer will be accepted as correct.<\/li>\n<\/ul>\n<h1><strong>Idea<\/strong><\/h1>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2459\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/813-ep179.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/813-ep179.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/813-ep179-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/813-ep179-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p>DP, use dp[k][i] to denote the largest average sum of partitioning first i elements into k groups.<\/p>\n<h3><strong>Init<\/strong><\/h3>\n<p>dp[1][i] = sum(a[0] ~ a[i &#8211; 1]) \/ i, for i in 1, 2, &#8230; , n.<\/p>\n<h3><strong>Transition<\/strong><\/h3>\n<p>dp[k][i] = max(dp[k &#8211; 1][j] + sum(a[j] ~ a[i &#8211; 1]) \/ (i &#8211; j)) for j in k &#8211; 1,&#8230;,i-1.<\/p>\n<p>that is find the best j such that maximize dp[k][i]<\/p>\n<p>largest sum of partitioning first j elements (a[0] ~ a[j &#8211; 1]) into k &#8211; 1 groups (already computed)<\/p>\n<p>+ average of a[j] ~ a[i &#8211; 1] (partition a[j] ~ a[i &#8211; 1] into 1 group).<\/p>\n<h3><strong>Answer<\/strong><\/h3>\n<p>dp[K][n]<\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<h1><strong>Solution 1: DP<\/strong><\/h1>\n<p>Time complexity: O(kn^2)<\/p>\n<p>Space complexity: O(kn)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 9 ms\r\nclass Solution {\r\npublic:\r\n  double largestSumOfAverages(vector&lt;int&gt;&amp; A, int K) {\r\n    const int n = A.size();\r\n    vector&lt;vector&lt;double&gt;&gt; dp(K + 1, vector&lt;double&gt;(n + 1, 0.0));\r\n    vector&lt;double&gt; sums(n + 1, 0.0);\r\n    for (int i = 1; i &lt;= n; ++i) {\r\n      sums[i] = sums[i - 1] + A[i - 1];\r\n      dp[1][i] = static_cast&lt;double&gt;(sums[i]) \/ i;\r\n    }\r\n    for (int k = 2; k &lt;= K; ++k)\r\n      for (int i = k; i &lt;= n; ++i)\r\n        for (int j = k - 1; j &lt; i; ++j)\r\n          dp[k][i] = max(dp[k][i], dp[k - 1][j] + (sums[i] - sums[j]) \/ (i - j));\r\n    return dp[K][n];\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ O(n) space<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true  \">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  double largestSumOfAverages(vector&lt;int&gt;&amp; A, int K) {\r\n    const int n = A.size();\r\n    vector&lt;double&gt; dp(n + 1, 0.0);\r\n    vector&lt;double&gt; sums(n + 1, 0.0);\r\n    for (int i = 1; i &lt;= n; ++i) {\r\n      sums[i] = sums[i - 1] + A[i - 1];\r\n      dp[i] = static_cast&lt;double&gt;(sums[i]) \/ i;\r\n    }\r\n    for (int k = 2; k &lt;= K; ++k) {\r\n      vector&lt;double&gt; tmp(n + 1, 0.0);\r\n      for (int i = k; i &lt;= n; ++i)\r\n        for (int j = k - 1; j &lt; i; ++j)\r\n          tmp[i] = max(tmp[i], dp[j] + (sums[i] - sums[j]) \/ (i - j));\r\n      dp.swap(tmp);\r\n    }\r\n    return dp[n];\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: DFS + memoriation\u00a0<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 10 ms\r\nclass Solution {\r\npublic:\r\n  double largestSumOfAverages(vector&lt;int&gt;&amp; A, int K) {\r\n    const int n = A.size();\r\n    m_ = vector&lt;vector&lt;double&gt;&gt;(K + 1, vector&lt;double&gt;(n + 1, 0.0));\r\n    sums_ = vector&lt;double&gt;(n + 1, 0.0);\r\n    for (int i = 1; i &lt;= n; ++i)\r\n      sums_[i] = sums_[i - 1] + A[i - 1];\r\n    return LSA(A, n, K);\r\n  }\r\nprivate:\r\n  vector&lt;vector&lt;double&gt;&gt; m_;\r\n  vector&lt;double&gt; sums_;\r\n  \r\n  \/\/ Largest sum of averages for first n elements in A paritioned into k groups\r\n  double LSA(const vector&lt;int&gt;&amp; A, int n, int k) {\r\n    if (m_[k][n] &gt; 0) return m_[k][n];\r\n    if (k == 1) return sums_[n] \/ n;\r\n    for (int i = k - 1; i &lt; n; ++i)\r\n      m_[k][n] = max(m_[k][n], LSA(A, i, k - 1) + (sums_[n] - sums_[i]) \/ (n - i));\r\n    return m_[k][n];\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u628a\u4e00\u4e2a\u6570\u7ec4\u5206\u6210k\u4e2a\u6bb5\uff0c\u6c42\u6bcf\u6bb5\u5e73\u5747\u503c\u548c\u7684\u6700\u5927\u503c\u3002 https:\/\/leetcode.com\/problems\/largest-sum-of-averages\/description\/ We partition a row of numbers\u00a0A\u00a0into at most\u00a0K\u00a0adjacent (non-empty) groups, then our score is the sum of the average of each group.&#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":[277,18,177,294,150],"class_list":["post-2449","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-average","tag-dp","tag-medium","tag-partial-sum","tag-partition","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2449","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=2449"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2449\/revisions"}],"predecessor-version":[{"id":3840,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2449\/revisions\/3840"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2449"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2449"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2449"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}