Java | Kadane | Explained w/ Diagrams
Two cases: \n1. Array sum is negative\n2. Array sum is positive\n\nIf we are dealing with case 1, then we wouldn\'t want to include a whole array because we cou
Two cases: \n1. Array sum is negative\n2. Array sum is positive\n\nIf we are dealing with case 1, then we wouldn\'t want to include a whole array because we could have a better result by cutting out any whole array in the maximum k-concatenated subarray.\n\nLet\'s then look at case 2:\nWithout the loss of generality, when array sum is positive, we can draw a diagram like this where our largest sum subarray is covered by white marker.\n\n![image](https://assets.leetcode.com/users/images/89a76d09-1457-4c56-8ace-bca1c9575eed_1649443304.003091.png)\n\nWhen each green segement (array) sum is positive, we can disregard the middle segemnt and simplify this into head & tail (`k = 2`) case like the below shows. When we run kadane through it, we can possibly find two cases: \n1. The largest subarray is marked blue where it crosses the array\n\n2. The largest subarray is marked red where it stays in the same array. \n\n\n![image](https://assets.leetcode.com/users/images/b876f882-c0ad-4e3c-9c07-7f3e3816896a_1649443356.6162713.png)\nIt is important to recognize that case 2 can only happen when the yellow segment is more negative than how positive red segment is; otherwise, the red segment would have included the yellow segment to combine the next red segment to yield a better outcome. Note that Yellow segment is the start and end segment of an array, so this actually means is that the whole subarray sum will be negative, which means case 2 does not fall under the case where array sum is positive.\n\nWith that out of the way, we can write the following solution:\n\n```Java\nclass Solution {\n    public int kConcatenationMaxSum(int[] arr, int k) {\n        int kadane = 0, cur = 0, n = arr.length, m = (int)(1e9 + 7), sum = Arrays.stream(arr).sum();\n        for (int i = 0; i < Math.min(2, k) * n; i++){\n            int j = i % n;\n            cur = Math.max(cur + arr[j], arr[j]);\n            kadane = Math.max(kadane, cur);\n        }\n\n        return k <= 2 || kadane > kadane + 1L * (k - 2) * sum? \n            kadane % m : (int)((kadane + 1L * (k - 2) * sum) % m);\n    }\n}\n\n// OR, we can find the max suffix and max prefix sum like the below solution shows.\n// I wasn\'t sure if the kadane across 2-concatenated arrays guarantees they are connected, \n// so I wrote the below first, then refined it into the solution above.\n//\n// class Solution {\n//     public int kConcatenationMaxSum(int[] arr, int k) {\n//         int kadane = 0, cur = 0, n = arr.length, m = (int)(1e9 + 7);\n//         for (int i = 0; i < Math.min(2, k) * n; i++){\n//             int j = i % n;\n//             cur = Math.max(cur + arr[j], arr[j]);\n//             kadane = Math.max(kadane, cur);\n//         }\n//         if (k <= 2)\n//             return kadane % m;\n\n//         int min = 0, max = 0, sum = 0;\n//         for (int i = 0 ; i < n; i++){\n//             sum += arr[i];\n//             min = Math.min(sum, min);\n//             max = Math.max(sum, max);\n//         }\n\n//         long other = (sum - min) + 1L * sum * (k - 2) + max;\n//         return other > kadane? (int)(other % m) : kadane % m;\n//     }\n// }\n```
['Java']