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: