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 = 3Output
9Repeating
arr three times gives [1, 2, 1, 2, 1, 2], whose maximum sub-array sum is 9.Example 2
Input
arr = [1,-2,1], k = 5Output
2The maximum sub-array sum after repeating
arr five times is 2.Constraints
- 1 <= arr.length <= 10^5
- 1 <= k <= 10^5
- -10^4 <= arr[i] <= 10^4