[JAVA] Java Solution with Explanation
The key is to figure out couple of cases that the answer could be derived from.\nCase 1: when k == 1, then the question is just asking max subarray sum since th
The key is to figure out couple of cases that the answer could be derived from.\nCase 1: when k == 1, then the question is just asking max subarray sum since there\'s only 1 array\nCase 2: when k > 1:\n- Case2(1): when sum >= 0: we can use ((k - 2) * sum of array) as \'free\' sum since they are positive and why not add them to our answer. Then, only add max prefix sum and max suffix sum from the rest two arrays to add to our final answer.\n- Case2(2): when sum < 0: if sum < 0, there\'s no need to add any of (k - 2) \'free\' sum, they are only going to make our final answer smaller. So we only pick the max prefix sum + max suffix sum as our answer.\n- Note that for both cases in  case2, we need also compare final answer with kaden.\n\nHope it helpes.\n```\npublic static int mod = (int)(Math.pow(10, 9) + 7);\npublic int kConcatenationMaxSum(int[] arr, int k) {\n\t// 3 cases to consider:\n\t// case1: max = max subarray (k == 1)\n\t// case2: max = max(kaden, maxPrefixSum + maxSuffixSum + (k - 2) * sum) (sum >=0 && k > 1)\n\t// case3: max = max(kaden, maxPrefixSum + maxSuffixSum) (sum < 0 && k > 1)\n\n\tint n = arr.length;\n\tlong sum = 0;\n\t// calculate sum of whole array\n\tfor (int i = 0; i < n; i++) {\n\t\tsum += arr[i];\n\t}\n\tint kaden = kadenAlg(arr);\n\t// case1\n\t// if only 1 array, then answer is the max subarray sum\n\tif (k == 1) {\n\t\treturn kaden;\n\t}  \n\t// calculate max value of prefix sum and max value of suffix sum\n\tlong prefixSum = 0;\n\tlong suffixSum = 0;\n\tlong maxPrefixSum = 0;\n\tlong maxSuffixSum = 0;\n\tfor (int i = 0; i < n; i++) {\n\t\tprefixSum = (prefixSum+ arr[i]) % mod;\n\t\tmaxPrefixSum = Math.max(maxPrefixSum, prefixSum);\n\t}\n\tfor (int i = n - 1; i >= 0; i--) {\n\t\tsuffixSum = (suffixSum + arr[i]) % mod;\n\t\tmaxSuffixSum = Math.max(maxSuffixSum, suffixSum);\n\t}\n\n\t// case 2:\n\tif (sum >= 0) {\n\t\treturn Math.max(kaden, (int)((sum * (k - 2)  + maxSuffixSum + maxPrefixSum) % mod));\n\t}\n\t// case 3:\n\telse {\n\t\treturn Math.max(kaden, (int)((maxSuffixSum + maxPrefixSum) % mod));\n\t}\n}\npublic int kadenAlg(int[] arr) {\n\tlong maxSoFar = 0, maxEndingHere = 0;\n\tfor (int i = 0; i < arr.length; i++) {\n\t\tmaxEndingHere = (maxEndingHere + arr[i]) % mod;\n\t\tif (maxEndingHere < 0) maxEndingHere = 0;\n\t\telse {\n\t\t\tmaxSoFar = Math.max(maxSoFar, maxEndingHere);\n\t\t}\n\t}\n\treturn (int)maxSoFar;\n}\n\n```
['Java']