{"id":5553,"date":"2019-09-15T15:28:53","date_gmt":"2019-09-15T22:28:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5553"},"modified":"2019-09-16T21:32:46","modified_gmt":"2019-09-17T04:32:46","slug":"leetcode-1191-k-concatenation-maximum-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1191-k-concatenation-maximum-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1191. K-Concatenation Maximum Sum"},"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 1191. K-Concatenation Maximum Sum - \u5237\u9898\u627e\u5de5\u4f5c EP269\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/-T19A8DvD6U?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 an integer array&nbsp;<code>arr<\/code>&nbsp;and an integer&nbsp;<code>k<\/code>, modify the array by repeating it&nbsp;<code>k<\/code>&nbsp;times.<\/p>\n\n\n\n<p>For example, if&nbsp;<code>arr&nbsp;= [1, 2]<\/code>&nbsp;and&nbsp;<code>k = 3&nbsp;<\/code>then the modified array will be&nbsp;<code>[1, 2, 1, 2, 1, 2]<\/code>.<\/p>\n\n\n\n<p>Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be&nbsp;<code>0<\/code>&nbsp;and its sum in that case is&nbsp;<code>0<\/code>.<\/p>\n\n\n\n<p>As the answer can be very large, return the answer&nbsp;<strong>modulo<\/strong>&nbsp;<code>10^9 + 7<\/code>.<\/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> arr = [1,2], k = 3\n<strong>Output:<\/strong> 9\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> arr = [1,-2,1], k = 5\n<strong>Output:<\/strong> 2\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> arr = [-1,-2], k = 7\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;= 10^5<\/code><\/li><li><code>1 &lt;= k &lt;= 10^5<\/code><\/li><li><code>-10^4 &lt;= arr[i] &lt;= 10^4<\/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\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269.png\" alt=\"\" class=\"wp-image-5560\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269-2.png\" alt=\"\" class=\"wp-image-5561\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/09\/1191-ep269-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>This problem can be reduced to maxSubarray.<br>If k &lt; 3: return maxSubarray(arr * k)<br>ans1 = maxSubarray(arr * 1)<br>ans2 = maxSubarray(arr * 2)<br>ans = max([ans1, ans2, ans2 + sum(arr) * (k &#8211; 2)])<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: 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++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int kConcatenationMaxSum(vector<int>& arr, int k) {\n    constexpr int kMod = 1e9 + 7;\n    auto maxSum = [&arr](int r) {\n      long sum = 0;\n      long ans = 0;\n      for (int i = 0; i < r; ++i) {\n        for (long a : arr) {\n          sum = max(0L, sum += a);          \n          ans = max(ans, sum);\n        }\n      }\n      return ans;\n    };\n    if (k < 3) return maxSum(k) % kMod;\n    long ans1 = maxSum(1);\n    long ans2 = maxSum(2);    \n    long sum = accumulate(begin(arr), end(arr), 0L);\n    return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array&nbsp;arr&nbsp;and an integer&nbsp;k, modify the array by repeating it&nbsp;k&nbsp;times. For example, if&nbsp;arr&nbsp;= [1, 2]&nbsp;and&nbsp;k = 3&nbsp;then the modified array will be&nbsp;[1, 2,&#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,177,376,182],"class_list":["post-5553","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","tag-on","tag-reduction","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5553","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=5553"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5553\/revisions"}],"predecessor-version":[{"id":5562,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5553\/revisions\/5562"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5553"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5553"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5553"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}