1191. K-Concatenation Maximum Sum
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 <= 105
1 <= 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) \times s + mxPre + 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)$. Here, $n$ is the length of the array $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 |
|