JAVA Solution with Easy Explanation Beat 100%
3 cases:\n1. maximum sum is located inside the array without any concatenation ( this is refer to 53. Maximum Subarray)\n2. if sum of array is negative - maximu
3 cases:\n1. maximum sum is located inside the array without any concatenation ( this is refer to 53. Maximum Subarray)\n2. if sum of array is negative - maximum sum is over somewhere after two array concatenation\n3. if sum of the array is positive - maximum sum is based on case 2 + (k - 2) * sum \n\n```\nclass Solution {\n    \n    int modulo = 1000000007;\n    \n    public int kConcatenationMaxSum(int[] arr, int k) {\n        \n        int n = arr.length;\n        int maxSoFar = arr[0];\n        int maxEndingHere = arr[0];\n        for(int i = 1; i < n; i++){\n            maxEndingHere = Math.max(maxEndingHere + arr[i], arr[i]);\n            maxSoFar = Math.max(maxSoFar, maxEndingHere);\n        }\n        \n        if(k < 2) return maxSoFar;\n        \n        int leftSum = arr[0];\n        int rightSum = arr[n - 1];\n        int lMax = Math.max(0, arr[0]);\n        int rMax = Math.max(0, arr[n-1]);\n        \n        for(int i = 1; i < n; i++){\n            leftSum += arr[i];\n            lMax = Math.max(lMax, leftSum);\n        }\n        \n        for(int i = n - 2; i >= 0; i--){\n            rightSum += arr[i];\n            rMax = Math.max(rMax, rightSum);\n        }\n        \n        int headTailMax = lMax + rMax;\n\n        if(leftSum < 0) return Math.max(maxSoFar, headTailMax);\n        \n        else return Math.max(maxSoFar, (int)(headTailMax + ((k - 2) * (long)leftSum) % modulo));\n            \n    }\n}\n```
['Java']