[LeetCode] K-Concatenation Maximum Sum

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
long long totalSum = 0;
long long answer = 0;
long long maxValue = 0;
long long minValue = 0;
for(int i = 0; i < arr.size(); i++) {
totalSum += arr[i];
maxValue = max(maxValue, totalSum);
minValue = min(minValue, totalSum);

answer = max(answer, totalSum - minValue);
}

if(k > 1) {
answer = max(answer, max(totalSum - minValue + maxValue, totalSum * (k - 1) + max(totalSum - minValue, maxValue)));

if(k > 2) {
answer = max(answer, totalSum * (k - 2) + totalSum - minValue + maxValue);
}
}

return max(totalSum * k, answer) % 1000000007;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/01/20/PS/LeetCode/k-concatenation-maximum-sum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.