# 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.

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^5
• 1 <= 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);
}
};