# K-Concatenation Maximum Sum in Python

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 `10^9 + 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 <= 10^5`

`1 <= k <= 10^5`

`-10^4 <= arr[i] <= 10^4` ```

## Solution:

``````class Solution(object):
def kConcatenationMaxSum(arr, k):
currsum, max_sum = arr[0], arr[0]
for i in range(1, len(arr)):
currsum = max(arr[i], currsum + arr[i])
max_sum = max(max_sum, currsum)
return max_sum

def prefix(arr):
currsum, max_val = 0, float('-inf')
for i, val in enumerate(arr):
currsum += val
max_val = max(max_val, currsum)
return max_val

def suffix(arr):
currsum, max_val = 0, float('-inf')
for i in range(len(arr)-1, -1, -1):
currsum += arr[i]
max_val = max(max_val, currsum)
return max_val

if not arr:
return 0
if k == 1:
return max(0, kadane(arr)) % (10 ** 9 + 7)
else:
return max(0, max((prefix(arr) + suffix(arr) + (k-2)*max(sum(arr), 0), kadane(arr)))) % (10 ** 9 + 7)

arr = [1,2]
k = 3
print(Solution.kConcatenationMaxSum(arr, k))