# 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 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
Approach 1: think about the kind of different possibilities there are.
# Code (Python)
Approach 1:
def kConcatenationMaxSum(self, nums: List[int], k: int) -> int:
# idea explained: https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1191-k-concatenation-maximum-sum/
mod_value = 1e9 + 7
if k == 1:
return max(0, self._max_sum(nums, 1))
one_copy, two_copies = self._max_sum(nums, 1), self._max_sum(nums, 2)
# when max is one_copy: sum(nums) < 0 but there's a subarray > 0
# when max is two_copies: sum(nums) < 0 but prefix and suffix sums are both > 0
# when max is two_copies + (k - 2) * sum(nums): sum(nums) > 0, then exclude minimum prefix and suffix from each end
return int(max(0, one_copy, two_copies, two_copies + (k - 2) * sum(nums)) % mod_value)
def _max_sum(self, nums, copies):
max_sum = -float('inf')
total = 0
for _ in range(copies):
for num in nums:
total = max(total + num, num)
max_sum = max(max_sum, total)
return max_sum
# Code (C++)
Approach 1:
Approach 2: