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) \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
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int kConcatenationMaxSum(int[] arr, int k) {
long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
for (int x : arr) {
s += x;
mxPre = Math.max(mxPre, s);
miPre = Math.min(miPre, s);
mxSub = Math.max(mxSub, s - miPre);
}
long ans = mxSub;
final int mod = (int) 1e9 + 7;
if (k == 1) {
return (int) (ans % mod);
}
long mxSuf = s - miPre;
ans = Math.max(ans, mxPre + mxSuf);
if (s > 0) {
ans = Math.max(ans, (k - 2) * s + mxPre + mxSuf);
}
return (int) (ans % mod);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
for (int x : arr) {
s += x;
mxPre = max(mxPre, s);
miPre = min(miPre, s);
mxSub = max(mxSub, s - miPre);
}
long ans = mxSub;
const int mod = 1e9 + 7;
if (k == 1) {
return ans % mod;
}
long mxSuf = s - miPre;
ans = max(ans, mxPre + mxSuf);
if (s > 0) {
ans = max(ans, mxPre + (k - 2) * s + mxSuf);
}
return ans % mod;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func kConcatenationMaxSum(arr []int, k int) int {
var s, mxPre, miPre, mxSub int
for _, x := range arr {
s += x
mxPre = max(mxPre, s)
miPre = min(miPre, s)
mxSub = max(mxSub, s-miPre)
}
const mod = 1e9 + 7
ans := mxSub
if k == 1 {
return ans % mod
}
mxSuf := s - miPre
ans = max(ans, mxSuf+mxPre)
if s > 0 {
ans = max(ans, mxSuf+(k-2)*s+mxPre)
}
return ans % mod
}
|
