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 109 + 7.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	1 &lt;= k &lt;= 105
	-104 &lt;= arr[i] &lt;= 104


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        dp = [0] * len(arr) # sum of the best subarry ends at i
        dp[0] = arr[0]
        total = arr[0] # total sum 
        right = arr[0] # sum of the best subarray starts at 0
        
        p = 1 
        while p < len(arr):
            dp[p] = max(arr[p], dp[p-1] + arr[p])
            total += arr[p] 
            right = max(right, total)
            
            p += 1
        
        isolated = max(dp + [0]) # max sum
        left = dp[-1] # sum of the best subarray ends at n-1
        
        if k == 1:
            
            return isolated  % (10**9 + 7)
        
        return max(left + right + max(0,(k-2) * total), isolated) % (10**9 + 7)
class Solution {
    int mod = 1000000007;
    
    public int kadane(int[] a ){
        int curr = 0;
        int max = Integer.MIN_VALUE;
        for(int i: a )
        {
            curr+=i;
            if(curr<0 )
                curr =0;
            max = Math.max(max,curr );
            
        }
        
        return max%mod ;
    }
    public int kConcatenationMaxSum(int[] arr, int k) {
        
        int n = arr.length;
        if(k==1 ) 
            return kadane(arr);
        int[] temp = new int[2*n]; 
        for(int i=0;i<n;i++){
            temp[i]=arr[i];
            temp[n+i] =arr[i];
        }
        if(k==2 )
            return kadane(temp)%mod;
        
        long sum = 0;
        for(int i: arr) 
            sum+=i;
        
        if(sum>=0 )
            return (int)( (kadane(temp)%mod)+ ((sum%mod) * (k-2)%mod) %mod);
        else
            return (kadane(temp)%mod );
    }
}
class Solution {
public:

    // Compute max score across all cases
    //  1. (arr_sum * k) [array sum is positive]
    //  2. (subarray_sum) [k == 1]
    //  3. if k > 1:
    //          if k == 2: lm + rm
    //          else: lm + (arr_sum * (k-2)) + rm

    // For case:3, instead of running over the entire modified array,
    //  we can just add (arr_sum * (k-2)) to the 's' instead.

    int kConcatenationMaxSum(vector<int>& arr, int k) {
        
        const int n = arr.size();
        int64_t s{}, min_s{}, max_score{INT_MIN};
        
        // This loop computes the answer for case:2
        for(int i=0; i<n; i++){
            s += arr[i];
            max_score = max(max_score, s - min_s);
            min_s = min(min_s, s);
        }
        
        if(k > 1){
            // Condition for case:3 part:2
            // At this point, 's' holds the sum of all numbers in 'arr'
            if(k > 2) s = max(s, s + s * (k - 2));
            // Base logic for case:3 part:1
            for(int i=0; i<n; i++){
                s += arr[i];
                max_score = max(max_score, s - min_s);
                min_s = min(min_s, s);
            }
        }

        // If all numbers are positive, case:1 is automatically computed with
        //  the method given above.
        //  Because (for an array with all positive elements):
        //      (max_score [after first loop]) == (arr_sum)
        //      s is updated to (s + s * (k - 2))
        //      Finally, s (and subsequently max_score) is also updated to (arr_sum * k)

        // Apply modulo on answer and convert to int
        int ans = static_cast<int>(max_score % (1000000000 + 7));
        // Subarray can have length == 0 (and sum == 0)
        if(ans < 0) return 0;
        else return ans;
    }
};
var kConcatenationMaxSum = function(arr, k) {
    var MOD = 1000000007;
    let sum = arr.reduce((a,b)=>a+b);
    if(k>1) arr.push(...arr);
    let temp = 0, result = 0;
     for(i=0;i<arr.length;i++){
          temp = Math.max(arr[i],arr[i]+temp);
          if(temp>result) result = temp;
        }
    return (sum>0&&k>2) ? (result+sum*(k-2))%MOD : result%MOD;
};
K-Concatenation Maximum Sum