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):
        def kadane(arr):
            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)

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

# Answer 2
arr = [1,-2,1]
k = 5
print(Solution.kConcatenationMaxSum(arr, k))

# Answer 3
arr = [-1,-2]
k = 7
print(Solution.kConcatenationMaxSum(arr, k))