> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/k-concatenation-maximum-sum.md).

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

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