Description
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
Solutions
Solution 1: Prefix Sum + Case Discussion
We denote the sum of all elements in the array arr as s, the maximum prefix sum as mxPre, the minimum prefix sum as miPre, and the maximum subarray sum as mxSub.
We traverse the array arr. For each element x, we update s = s + x, mxPre = max(mxPre, s), miPre = min(miPre, s), mxSub = max(mxSub, s - miPre).
Next, we consider the value of k:
- When k = 1, the answer is mxSub.
- When k \ge 2, if the maximum subarray spans two arr, then the answer is mxPre + mxSuf, where mxSuf = s - miPre.
- When k \ge 2 and s > 0, if the maximum subarray spans three arr, then the answer is (k - 2) × s + mxPre + mxSuf.
Finally, we return the result of the answer modulo 109 + 7.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array arr.
class Solution: def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: s = mx_pre = mi_pre = mx_sub = 0 for x in arr: s += x mx_pre = max(mx_pre, s) mi_pre = min(mi_pre, s) mx_sub = max(mx_sub, s - mi_pre) ans = mx_sub mod = 10**9 + 7 if k == 1: return ans % mod mx_suf = s - mi_pre ans = max(ans, mx_pre + mx_suf) if s > 0: ans = max(ans, (k - 2) * s + mx_pre + mx_suf) return ans % mod(code-box)
