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; } };
|