C++ Short and Easy to understand
Thinking Process:\nFirst look at this question, makes me think of Leetcode 53. Maximum Subarray.\n\nint maxSubArray(vector<int>& nums) {\n\tint cur = nums[0], r
**Thinking Process:**\nFirst look at this question, makes me think of [Leetcode 53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/).\n```\nint maxSubArray(vector<int>& nums) {\n\tint cur = nums[0], result = cur;\n\tfor (int i = 1; i < nums.size(); i++) {\n\t\tcur = max(nums[i], cur + nums[i]);\n\t\tresult = max(result, cur);\n\t}\n\treturn result;\n}\n```\n\nA naive way is to loop input array k times and use the same idea mentioned above. And of course it\'s a TLE.\n\n```\nint kConcatenationMaxSum(vector<int>& arr, int k) {\n\tint result = 0, cur_max = 0;\n\tint M = 1e9 + 7;\n\tfor (int i = 0; i < k; i++) {\n\t\tfor (int n : arr) {\n\t\t\tcur_max = max(cur_max + n, n) % M;\n\t\t\tresult = max(result, cur_max) % M;\n\t\t}\n\t}\n\treturn result;\n}\n```\n\nBut now I have the result for k == 1 at least, now let\'s think about k == 2. We can easily find that there are 3 cases for k == 2:\n\n1. max subarray is somewhere in the middle and the second repeat does not help at all. ex. arr = [-1,  1,  -1], repeat twice, arr2 = [-1, 1, -1, -1, 1, -1], max subarray is still 1;\n2. max subarray is somewhere in the middle and the second repeat can offer some help. ex. arr = [-1, 4, -1], repeat twice, arr2 = [-1, 4, -1, -1, 4 ,-1], max subarray increases from 4 to [4, -1, -1, 4] -> 6. Further, we can easily find that the extra offer is the sum of the arr = [-1, 4, -1] -> 2; **sum > 0 is the key difference from case 1**. And we can easily extend this case to any k > 2 as well, result = result + (k - 1) * sum; \n3. max subarray is at the end of the array and the head of second repeat can offer some help. ex. arr = [1, -4, 1], repeat twice, arr2 = [1, -4, 1, 1, -4, 1], max subarray increases from 1 to 2; This is a special case which will not be affected by more repeated arrays. \n\nAs we think through k == 2, we already have the idea to extend to any k!\n\n**Code:**\n```\nint kConcatenationMaxSum(vector<int>& arr, int k) {\n\tlong result = 0, cur_max = 0, sum = 0;\n\tint M = 1e9 + 7;\n\t// basic solution from Leetcode 53\n\tfor (int i = 0; i < arr.size(); i++) {\n\t\tcur_max = max(cur_max + arr[i], (long)arr[i]);\n\t\tresult = max(result, cur_max);\n\t\tsum += arr[i];\n\t}\n\t// k < 2, return result from basic solution\n\tif (k < 2) return result % M;\n\t// sum > 0, case 2\n\tif (sum > 0) return (result + (k - 1) * sum) % M;\n\t// another round to catch case 3\n\tfor (int i = 0; i < arr.size(); i++) {\n\t\tcur_max = max(cur_max + arr[i], (long)arr[i]);\n\t\tresult = max(result, cur_max);\n\t}\n\treturn result % M;\n}\n```
[]