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 109 + 7.
Example 1:
Input: arr = [1, 2], k = 3
Output: 9
Explanation:
The concatenated array is [1, 2, 1, 2, 1, 2].
The maximum-sum subarray is the entire array, with sum 1 + 2 + 1 + 2 + 1 + 2 = 9.
Example 2:
Input: arr = [1, -2, 1], k = 5
Output: 2
Explanation:
The concatenated array is [1, -2, 1, 1, -2, 1, 1, -2, 1, 1, -2, 1, 1, -2, 1].
The maximum-sum subarray is [1, 1], formed by the last element of one copy and the first element of the next copy, with sum 1 + 1 = 2.
Example 3:
Input: arr = [-1, -2], k = 7
Output: 0
Explanation:
Every element in the concatenated array is negative, so no subarray has a positive sum. Therefore, the maximum possible sum is 0.
Constraints:
1 <= arr.length <= 1051 <= k <= 105-104 <= arr[i] <= 104