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

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