Java 8-line solution (Kadane's) with explanation
Thanks @votrubac for inspiring me.\n\nFirst of all, you need to know what is Kadane\'s Algorithm to solve "the largest subarray sum". It\'s a very elegant solut
Thanks @votrubac for inspiring me.\n![image](https://assets.leetcode.com/users/zdxiq125/image_1577780621.png)\nFirst of all, you need to know what is [Kadane\'s Algorithm](https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6) to solve ["the largest subarray sum"](https://en.wikipedia.org/wiki/Maximum_subarray_problem). It\'s a very elegant solution using dynamic programming. We can easily get `maxSoFar` by `maxOfEnd[i]` which represent the largest sum of subarray(s) ended by `arr[i]`. With the example above, the result is `55 + 66 = 121`.\n```java\nint largestSubarraySum(int[] arr) {\n\tint maxOfEnd, maxSoFar;\n\tmaxSoFar = maxOfEnd = arr[0] > 0 ? arr[0] : 0;\n\tfor (int i = 1; i < arr.length; i++) {\n\t\tmaxOfEnd = Math.max(maxOfEnd + arr[i], arr[i]);\n\t\tmaxSoFar = Math.max(maxOfEnd, maxSoFar);\n\t}\n\treturn maxSoFar;\n}\n```\n![image](https://assets.leetcode.com/users/zdxiq125/image_1577781579.png)\nWhen it comes to concatenated arrays, the definition of general subarray has changed because of the subarray can go through the "bound". But if we bound subarray by `arr.length`, problem becomes another one with `arr`: number of the subarrays are doubled and all the subarrays consist of two types.\n* **Type 1: Formal**, sum of `formal_subarray(i, j)` is:\n`arr[i] + arr[i+1] + ... + arr[j]`, where `0 <= i <= j < arr.length`\n* **Type 2: Non-formal**, sum of `nonformal_subarray(i, j)` is\n`arr[0] + arr[1] + ... + arr[i] + arr[j] + arr[j+1] + ... + arr[arr.lengh-1]`, where `0 <= i <= j < arr.length`\n\nAfter calculate the "largest subarray sum" by concatenate two array, we have almost reached the goal.\n```java\nint largestSubarraySum(int[] arr) {\n\tint maxOfEnd, maxSoFar, len = arr.length;\n\tmaxSoFar = maxOfEnd = arr[0] > 0 ? arr[0] : 0;\n\tfor (int i = 1; i < len * 2; i++) {\n\t\tmaxOfEnd = Math.max(maxOfEnd + arr[i % len], arr[i % len]);\n\t\tmaxSoFar = Math.max(maxOfEnd, maxSoFar);\n\t}\n\treturn maxSoFar;\n}\n```\nLet\'s go to the final part. Above algorithm exactly gives `maxSoFar = 185` (Pic iii, the RED region). It\'s neither **Formal** one nor **Non-formal** one. So what\'s this?\n![image](https://assets.leetcode.com/users/zdxiq125/image_1577809682.png)\nIf we divide it into two parts: BLUE and GREEN, then we can see more about it. It\'s just a **Formal** subarray (BLUE region) plus a whole array sum (GREEN region). `[55, 66]` is the largest among **Formal** and **Non-formal** ones, but it can still be larger when extended by an array length if `sum(arr)` is **positive**. When `k` grows up, the maximum sequence grows up as well. So here is the answer. Take care if `k == 1`.\n```java\nclass Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        if (arr == null || arr.length == 0) return 0;\n        long maxOfEnd = arr[0] > 0 ? arr[0] : 0L, maxSoFar = maxOfEnd, sum = arr[0];\n        for (int i = 1; i < Math.min(k, 2) * arr.length; i++) {\n            maxOfEnd = Math.max(maxOfEnd + arr[i % arr.length], arr[i % arr.length]);\n            maxSoFar = Math.max(maxOfEnd, maxSoFar);\n            if (i < arr.length) sum += arr[i];\n        }\n        while (sum > 0 && --k >= 2)\n\t\t\tmaxSoFar = (maxSoFar + sum) % 1000000007;\n        return (int) maxSoFar;\n    }\n}\n```\n**UPDATE**:\nWe declare the summary of `arr` as `sum(arr)` and concatenated array of repeating `arr` `k` times as `carr(k)` (`k >= 2`), then any subarray in  `carr(k)` can be written as the following formats.\n* `formal(i, j) + carr(n)`, where `n = 0, 1, 2, ..., k - 1` and `0 <= i <= j <= len(arr) - 1`\n* `nonformal(i, j) + carr(m)`, where `m = 0, 1, 2, ..., k - 2` and `0 <= i <= j <= len(arr) - 1`\n\nObviously, when `sum(arr) <= 0`, any subarray(s) whose length greater than `len(arr)` won\'t produce a larger sum compare to **Formal**/**Non-formal** ones.\nFurthermore, when `sum(arr) > 0`:\n* sum of `formal(i, j) + carr(n)` is `sum(formal(i, j)) + sum(arr) + r * sum(arr)`\n* sum of `nonformal(i, j) + carr(m)` is `sum(nonformal(i, j)) + r * sum(arr)`\n\nNow, `r` ranges from `0` to `k - 2`. That\'s why two concatenated arrays is the key to the answer. The second example of (iv) shows two largest cases each result from a **Formal** one (plus an `arr`) and a **Non-formal** one.\n![image](https://assets.leetcode.com/users/zdxiq125/image_1577938646.png)\n
[]