Leetcode•Oct 15, 2026
K-Concatenation Maximum Sum
Hazrat Ali
Leetcode
For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.
As the answer can be very large, return the answer modulo 109 + 7.
Example 1:
Input: arr = [1,2], k = 3 Output: 9
Example 2:
Input: arr = [1,-2,1], k = 5 Output: 2
Example 3:
Input: arr = [-1,-2], k = 7 Output: 0
Solution
var kConcatenationMaxSum = function(arr, k) {
const MOD = 1000000007;
let total = 0;
let maxEnding = 0;
let maxSum = 0;
for (const num of arr) {
total += num;
maxEnding = Math.max(0, maxEnding + num);
maxSum = Math.max(maxSum, maxEnding);
}
if (k === 1) {
return maxSum % MOD;
}
let prefixSum = 0;
let maxPrefix = 0;
for (const num of arr) {
prefixSum += num;
maxPrefix = Math.max(maxPrefix, prefixSum);
}
let suffixSum = 0;
let maxSuffix = 0;
for (let i = arr.length - 1; i >= 0; i--) {
suffixSum += arr[i];
maxSuffix = Math.max(maxSuffix, suffixSum);
}
let answer = maxPrefix + maxSuffix;
if (total > 0) {
answer += (k - 2) * total;
}
answer = Math.max(answer, maxSum);
return answer % MOD;
};