JavaScript Solution - Using Kadane's Algorithm
The solution seems long and complicated, but if you walk through it step by step, it is actually pretty straightforward. The most difficult part about the probl
The solution seems long and complicated, but if you walk through it step by step, it is actually pretty straightforward. The most difficult part about the problem is understanding the different scenarios you will have when you have k that is greater than 1. I did not really try to explain it here, since I feel like there are some good explanations in other people\'s post.\nHowever, if you have any question that I can possible answer and help, please let met know. Thank you.\n\n```\nvar kConcatenationMaxSum = function(arr, k) {\n    const MOD = 1e9 + 7;\n    const n = arr.length;\n    \n    let max = arr[0]; // represent the max subarray sum of a single iteration of the original array\n    let curr = arr[0];\n    \n    // Kadane\'s Algorithm\n    for (let i = 1; i < n; i++) {\n        curr = Math.max(arr[i], curr + arr[i]);\n        max = Math.max(curr, max);\n    }\n    \n    // If we can\'t get a subarray with a sum that is greater than 0, then it is better to not get anything\n    if (max < 0) max = 0;\n    \n    let prefixSum = arr[n - 1];\n    let maxPrefix = arr[n - 1];\n    \n    // the prefix is from the back since we are going to use the back portion of the original array for the front of the subarray\n    for (let i = n - 2; i >= 0; i--) {\n        prefixSum += arr[i];\n        maxPrefix = Math.max(prefixSum, maxPrefix);\n    }\n    \n    let suffixSum = arr[0];\n    let maxSuffix = arr[0];\n    \n    // the suffix is the reverse of prefix where we are going to use the front portion of the original array for the back of the subarray\n    for (let i = 1; i < n; i++) {\n        suffixSum += arr[i];\n        maxSuffix = Math.max(suffixSum, maxSuffix);\n    }\n\n    let sum = 0;\n    \n    // calculate the entire sum of the array\n    for (let i = 0; i < n; i++) {\n        sum += arr[i];\n    }\n    \n    // For k == 1, we just need to return the result from Kadane\'s Algorithm\n    if (k == 1) return max % MOD;\n    \n    \n    // The different scenarios of the max subarray sum that can form are:\n\t//\n    //  (1) max (max subarray sum from Kadane\'s Algorithm or 0 if the max sum < 0)\n\t//\n\t//  (2) maxPrefix + the sum of the original array * (k - 2) + maxSuffix. It is k - 2 since\n    //      we used an array for the maxPrefix and array for the maxSuffix.\n\t//\n    //  (3) maxPrefix + maxSuffix (this represent the max subarray from 2 concatenation of the original array)\n    \n\t\n    // If we have a sum greater than 0, then the maximum is between (1), (2), and (3) from the three scenarioes above\n    if (sum > 0) {\n        return Math.max(\n            max, // (1)\n\t\t\tmaxPrefix + (k - 2) * sum + maxSuffix, // (2)\n\t\t\tmaxPrefix + maxSuffix // (3)\n\t\t) % MOD;\n\t}\n   \n    // If the sum is less than 0, then the maximum is between (1) and (3) from the three scenarioes above\n    return Math.max(\n        max, // (1)\n        maxPrefix + maxSuffix // (3)\n    ) % MOD;\n};\n```
['Dynamic Programming', 'JavaScript']