1191. K-Concatenation Maximum Sum
SourceWeekly Contest 154 Q3DifficultyMediumRating1747
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
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
Solutions
Solution 1: Prefix Sum + Case Discussion
Thinking
After repeating \(\textit{arr}\) \(k\) times, an optimal subarray spans at most the whole concatenation. Kadane on one copy gives \(\textit{mxSub}\), plus the max prefix and min prefix (hence max suffix). For \(k=1\) that is the answer; otherwise also consider prefix+suffix, and if the total is positive add \(k-2\) full copies. \(k\) can be \(10^5\), so we never materialize the concatenation.
We denote the sum of all elements in the array \(\textit{arr}\) as \(s\), the maximum prefix sum as \(\textit{mxPre}\), the minimum prefix sum as \(\textit{miPre}\), and the maximum subarray sum as \(\textit{mxSub}\).
We traverse the array \(\textit{arr}\). For each element \(x\), we update \(s = s + x\), \(\textit{mxPre} = \max(\textit{mxPre}, s)\), \(\textit{miPre} = \min(\textit{miPre}, s)\), \(\textit{mxSub} = \max(\textit{mxSub}, s - \textit{miPre})\).
Next, we consider the value of \(k\):
- When \(k = 1\), the answer is \(\textit{mxSub}\).
- When \(k \ge 2\), if the maximum subarray spans two \(\textit{arr}\), then the answer is \(\textit{mxPre} + \textit{mxSuf}\), where \(\textit{mxSuf} = s - \textit{miPre}\).
- When \(k \ge 2\) and \(s > 0\), if the maximum subarray spans three \(\textit{arr}\), then the answer is \((k - 2) \times s + \textit{mxPre} + \textit{mxSuf}\).
Finally, we return the result of the answer modulo \(10^9 + 7\).
The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{arr}\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |