## 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 <= 105`
• `1 <= 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 [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);
};
``````
Copy The Code &

Input

cmd
arr = [1,2], k = 3

Output

cmd
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
``````
Copy The Code &

Input

cmd
arr = [1,2], k = 3

Output

cmd
9