1191. K-Concatenation Maximum Sum
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
10
9
+
7
10^9 + 7
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
<
=
a
r
r
.
l
e
n
g
t
h
<
=
10
5
1 <= arr.length <= 10^5
1<=arr.length<=105 -
1
<
=
k
<
=
10
5
1 <= k <= 10^5
1<=k<=105 -
−
10
4
<
=
a
r
r
[
i
]
<
=
10
4
-10^4 <= arr[i] <= 10^4
−104<=arr[i]<=104
From: LeetCode Link: 1191. K-Concatenation Maximum Sum
Solution:
Ideas:
Check the best subarray in 1 copy or 2 copies. If total array sum is positive, the middle copies add extra profit.
Code:
#define MOD 1000000007
long long kadane(int* arr, int arrSize, int times) {
long long best = 0;
long long cur = 0;
for (int t = 0; t < times; t++) {
for (int i = 0; i < arrSize; i++) {
cur += arr[i];
if (cur < 0) cur = 0;
if (cur > best) best = cur;
}
}
return best;
}
int kConcatenationMaxSum(int* arr, int arrSize, int k) {
long long sum = 0;
for (int i = 0; i < arrSize; i++) {
sum += arr[i];
}
if (k == 1) {
return kadane(arr, arrSize, 1) % MOD;
}
long long ans = kadane(arr, arrSize, 2);
if (sum > 0) {
ans += (long long)(k – 2) * sum;
}
return ans % MOD;
}
