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.
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 <= 10^51 <= k <= 10^5-10^4 <= arr[i] <= 10^4
Solution:
Two possible options:
1) Max sum in the array itself
2) Right most + Left most + (k-2)*sum if sum > 0 (prefix sum)
class Solution {
public:
int kConcatenationMaxSum(vector<int>& arr, int k) {
long long ans1 = 0;
long long cur = 0;
for(int i = 0; i < arr.size(); i++){
cur += arr[i];
if(cur < 0){
cur = 0;
}
ans1 = max(ans1, cur);
}
long long l = 0, r = 0;
vector<long long> sum(arr.size()+1, 0);
for(int i = 0;i < arr.size(); i++){
sum[i+1] = sum[i]+arr[i];
}
for(int i = 0;i <arr.size(); i++){
l = max(l, sum[i+1]);
r = max(r, sum[arr.size()] - sum[i]);
}
cout<<l<<" "<<r<<" "<<sum[arr.size()]<<"\n";
long long ans2 = l+r;
if(sum[arr.size()]>0 && k>2) ans2 += (k-2)*sum[arr.size()];
long long ans = max(ans1,ans2);
return ans % (1000000007LL);
}
};