Algorithm
Problem Name: 1191. K-Concatenation Maximum Sum
Given an integer array arr and an integer k, modify the array by repeating it k times.
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
Constraints:
1 <= arr.length <= 1051 <= k <= 105-104 <= arr[i] <= 104
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const kConcatenationMaxSum = function(arr, k) {
const MOD = 1e9 + 7,
INF = 1e4 + 1;
const kadane = (A, sum = 0, ans = -INF) => {
for (let x of A) {
sum = Math.max(0, sum + x);
ans = Math.max(ans, sum);
}
return [sum, ans];
};
const [sum1, ans1] = kadane(arr);
const [sum2, ans2] = kadane(arr, sum1);
const [sum3, ans3] = kadane(arr, sum2);
const delta1 = ans2 - ans1,
delta2 = ans3 - ans2;
return k == 1 || delta1 == 0
? ans1
: delta2 == 0
? ans2
: ans1 + ((delta1 * (k - 1)) % MOD);
};
Input
arr = [1,2], k = 3
Output
9
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kConcatenationMaxSum(self, arr: List[int], k: int, mod = 10 ** 9 + 7) -> int:
def Kadane(arr, res = 0, cur = 0):
for num in arr:
cur = max(num, num + cur)
res = max(res, cur)
return res
return ((k - 2) * max(sum(arr), 0) + Kadane(arr * 2) ) % mod if k > 1 else Kadane(arr) % mod
Input
arr = [1,2], k = 3
Output
9