Skip to content

1191. K-Concatenation Maximum Sum

Difficulty Topics

Description

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

Solution

k-concatenation-maximum-sum.py
class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        M = 10 ** 9 + 7
        def kadane(arr, res = 0, curr = 0):
            for num in arr:
                curr = max(num, curr + num)
                res = max(res, curr)
            return res

        return ((k - 2) * max(sum(arr), 0) + kadane(arr * 2) if k > 1 else kadane(arr)) % M