Watch 10 video solutions for K-Concatenation Maximum Sum, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 605,132 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= k <= 105-104 <= arr[i] <= 104