# K-Concatenation Maximum Sum

## Description

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

If `k = 1`, find the maximum sub-array sum in `arr`.

Else if `k = 2` or `sum(arr) <= 0`, find the maximum sub-array sum in `concat(arr, arr)`. (The maximum sub-array cannot contain a complete `arr` if `sum(arr) <= 0`)

Else find the maximum sub-array sum in `concat(arr, arr)` + `sum(arr) * (k - 2)`.

Let `max_sum[i]` be maximum sub-array sum ending with `arr[i]`. Then,

$$\text{max\_sum\[i]} = \text{sum}(\text{arr}\[0..i]) - \min\_{j \le i} \text{sum}(\text{arr}\[0..i])$$

Or $$\text{max\_sum}\[i] = \max(\text{arr}\[i], \text{max\_sum}\[i-1] + \text{arr}\[i])$$.

### Solution 1

```cpp
#define MOD (1'000'000'000 + 7)

class Solution {
public:
    int kConcatenationMaxSum(vector<int> &arr, int k) {
        long total_sum, min_sum, max_sum;
        total_sum = min_sum = max_sum = 0;
        for (int i = 0; i < arr.size(); ++i) {
            total_sum += arr[i];
            min_sum = min(total_sum, min_sum);
            max_sum = max(total_sum - min_sum, max_sum);
        }
        if (k == 1 || max_sum == 0)
            return max_sum;
        long onepass_sum = total_sum;
        for (int i = 0; i < arr.size(); ++i) {
            total_sum += arr[i];
            min_sum = min(total_sum, min_sum);
            max_sum = max(total_sum - min_sum, max_sum);
        }
        if (k == 2 || onepass_sum < 0)
            return max_sum % MOD;
        return (max_sum + (k - 2) * onepass_sum) % MOD;
    }
};
```

### Solution 2

```cpp
#define MOD (1'000'000'000 + 7)

class Solution {
public:
    int kConcatenationMaxSum(vector<int> &arr, int k) {
        int64_t total = accumulate(arr.begin(), arr.end(), 0);
        int sum = 0, max_sum = 0, n = arr.size();
        for (int i = 0; i < n * min(k, 2); ++i) {
            sum = max(arr[i % n], sum + arr[i % n]); // sum: maximum subarray sum ending with arr[i]
            max_sum = max(sum, max_sum);             // max_sum: maximum subarray sum in arr[0..i]
        }
        if (k <= 2 || total <= 0)
            return max_sum % MOD;
        return (max_sum + (k - 2) * total) % MOD;
    }
};
```