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 modulo10^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
class Solution {
int mod = (int) Math.pow(10,9)+7;
public long kadane(int[] arr){
long best=Long.MIN_VALUE;
long current=0;
for(int i=0;i<arr.length;i++){
current=(current+arr[i])%mod;
if(current>best){
best=current;
}
if(current<0){
current=0;
}
}
return best;
}
public long bestPrefix(int[] arr){
long best=Long.MIN_VALUE;
long current=0;
for(int i=0;i<arr.length;i++){
current=(current+arr[i])%mod;
if(current>best)
best=current;
}
return best;
}
public long bestSuffix(int[] arr){
long best=Long.MIN_VALUE;
long current=0;
for(int i=arr.length-1;i>=0;i--){
current=(current+arr[i])%mod;
if(current>best)
best=current;
}
return best;
}
public int kConcatenationMaxSum(int[] arr, int k) {
long kadane=kadane(arr);
if(k==1){
return (int)kadane;
}
long bestPrefix=bestPrefix(arr);
long bestSuffix=bestSuffix(arr);
long sum=0;
for(int x:arr){
sum=(sum+x)%mod;
}
if(sum>0){
return (int)Math.max(Math.max(kadane,(bestSuffix+((k-2)*sum)%mod+bestPrefix)%mod),0);
}
else{
return (int)Math.max(Math.max(kadane,(bestSuffix+bestPrefix)%mod),0);
}
}
}