# K-Concatenation Maximum Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-concatenation-maximum-sum)
Canonical: https://scaleengineer.com/dsa/problems/k-concatenation-maximum-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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`.

**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 <= 105`
* `1 <= k <= 105`
* `-104 <= arr[i] <= 104`

# Approaches
## Brute Force: Kadane's on Simulated Full Array
This approach simulates the process of running Kadane's algorithm on the full concatenated array of size `n * k` without actually constructing it. The `i`-th element of this virtual array can be accessed as `arr[i % n]`. We iterate `n * k` times, applying the Kadane's logic at each step. This is the most straightforward translation of a standard algorithm to the problem, but it ignores the performance implications of the large `k` value.
**Time:** O(N * K). The loop runs `n * k` times. Given `n, k <= 10^5`, this is too slow and will not pass the time constraints. · **Space:** O(1). We only use a few variables to keep track of the sums, regardless of the input size.
**Pros:** Simple to understand and implement.; Directly applies a well-known algorithm to the problem's structure.
**Cons:** Extremely inefficient for large values of `k` and `n`.; Will result in a Time Limit Exceeded (TLE) error on most platforms for the given constraints.
### Explanation
The most intuitive way to solve the problem is to imagine the fully concatenated array and find its maximum subarray sum. Since the concatenated array can be enormous (up to `10^5 * 10^5 = 10^{10}` elements), we cannot afford to build it in memory. However, we can simulate iterating over it. Kadane's algorithm is perfect for finding the maximum subarray sum in a single pass. We can apply it to our virtual array.

We can loop `n * k` times. In each step `i` of the loop, the corresponding element would be from the original `arr` at index `i % n`. We apply the standard Kadane's logic: keep track of the maximum sum ending at the current position and the overall maximum sum found so far. Since the subarray can be empty (sum 0), we initialize our overall maximum to 0. All sum accumulations should use a `long` data type to prevent integer overflow before the final modulo operation.

```java
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        long MOD = 1_000_000_007;
        int n = arr.length;
        long maxSoFar = 0;
        long maxEndingHere = 0;

        // This loop will be too long and cause Time Limit Exceeded
        // for the given constraints.
        for (long i = 0; i < (long)n * k; i++) {
            long currentElement = arr[(int)(i % n)];
            maxEndingHere += currentElement;

            if (maxEndingHere < 0) {
                maxEndingHere = 0;
            }
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return (int)(maxSoFar % MOD);
    }
}
```
### Algorithm
- The core idea is to simulate running Kadane's algorithm on the full concatenated array of size `n * k` without actually constructing it.
- The `i`-th element of this virtual array can be accessed as `arr[i % n]`.
- We maintain two `long` variables: `max_so_far` to store the maximum sum found anywhere (initialized to 0, for the empty subarray case), and `max_ending_here` to store the maximum sum of a subarray ending at the current position.
- We loop from `i = 0` to `n * k - 1`.
- In each iteration, we get the current element `arr[(int)(i % n)]` and add it to `max_ending_here`.
- We update `max_so_far = max(max_so_far, max_ending_here)`.
- If `max_ending_here` becomes negative, we reset it to 0, as a negative-sum prefix won't contribute to a larger maximum sum.
- Finally, we return `max_so_far` modulo `10^9 + 7`.

## Kadane's on a Doubled Array
This approach observes that the maximum subarray sum for `k` concatenations can be determined by analyzing the case for `k=2`. The maximum subarray can either be contained within a single copy of `arr` or span across two copies. Any further extension depends on the total sum of `arr`. By creating a temporary array of size `2*n` and running Kadane's on it, we can find the maximum sum for `k=2` and then extrapolate for larger `k` based on the total sum of `arr`.
**Time:** O(N). We iterate through `arr` to calculate `totalSum` (O(N)) and through `two_arr` to calculate its Kadane's sum (O(2N) = O(N)). The rest is O(1). · **Space:** O(N). We create an auxiliary array `two_arr` of size `2*n`.
**Pros:** Much more efficient than the brute-force approach, with linear time complexity.; Correctly identifies the repeating pattern and passes the time limits.; The logic is a good stepping stone to the fully optimal solution.
**Cons:** Uses extra space proportional to the input array size, which can be avoided.
### Explanation
A more optimized approach recognizes that we don't need to simulate the entire `n*k` iterations. The structure of the maximum subarray depends critically on the sum of the base array, `arr`.

Let `total_sum` be the sum of all elements in `arr`.

- **Case 1: `total_sum <= 0`**. If the sum of the array is non-positive, concatenating it more times won't increase the maximum subarray sum beyond what's achievable within two copies. Any subarray spanning more than two copies would have to include at least one full copy of `arr` in the middle, which would not increase (and likely decrease) the sum. Therefore, the maximum sum is confined to what can be found in `arr` concatenated with itself (`arr` + `arr`).

- **Case 2: `total_sum > 0`**. If the sum is positive, each full copy of `arr` contributes positively. The maximum subarray will be formed by taking the best possible subarray that spans one or two copies, and then adding the sum of the remaining `k-2` full copies of `arr`. The best sum over one or two copies can be found by running Kadane's algorithm on a doubled array (`arr` + `arr`).

This leads to an `O(N)` time and `O(N)` space solution.

```java
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        long MOD = 1_000_000_007;
        
        if (k == 1) {
            return (int)(Math.max(0L, kadane(arr)) % MOD);
        }

        long totalSum = 0;
        for (int x : arr) {
            totalSum += x;
        }

        int[] twoArr = new int[arr.length * 2];
        System.arraycopy(arr, 0, twoArr, 0, arr.length);
        System.arraycopy(arr, 0, twoArr, arr.length, arr.length);
        long maxSumForTwo = kadane(twoArr);

        if (totalSum <= 0) {
            return (int)(Math.max(0L, maxSumForTwo) % MOD);
        } else {
            long ans = maxSumForTwo + (k - 2) * totalSum;
            return (int)(Math.max(0L, ans) % MOD);
        }
    }

    private long kadane(int[] a) {
        long maxSoFar = Long.MIN_VALUE;
        long maxEndingHere = 0;
        for (int x : a) {
            maxEndingHere += x;
            if (maxSoFar < maxEndingHere) {
                maxSoFar = maxEndingHere;
            }
            if (maxEndingHere < 0) {
                maxEndingHere = 0;
            }
        }
        return maxSoFar;
    }
}
```
### Algorithm
- Handle the base case `k=1`. The answer is the result of Kadane's algorithm on the original `arr`, with a floor of 0.
- For `k > 1`, create a new array `two_arr` of size `2*n` by concatenating `arr` with itself.
- Calculate `max_sum_for_two`, the maximum subarray sum of `two_arr` using Kadane's algorithm.
- Calculate `total_sum` of the original `arr`.
- **If `total_sum <= 0`**: The answer is `max(0, max_sum_for_two)`. Concatenating more arrays won't help.
- **If `total_sum > 0`**: The answer is `max_sum_for_two + (k-2) * total_sum`. We take the best sum from two arrays and add the positive contribution of the remaining `k-2` arrays.
- The final result must be taken modulo `10^9 + 7`, ensuring it's non-negative.

## Optimal Mathematical Approach
This is the most efficient approach, which solves the problem in linear time and constant space. It relies on a mathematical breakdown of the problem into cases based on the total sum of the array `arr`. Instead of creating a doubled array, it calculates the necessary components (`kadane_max`, `max_prefix_sum`, `max_suffix_sum`, and `total_sum`) directly from `arr` in `O(N)` time and `O(1)` space, and then combines them to find the final answer.
**Time:** O(N). We perform a few passes over the array `arr`, each taking O(N) time. The rest of the calculations are O(1). · **Space:** O(1). We only use a constant number of variables to store the calculated sums.
**Pros:** Most efficient solution in both time (O(N)) and space (O(1)).; Avoids creating any large intermediate data structures.
**Cons:** The logic is more complex and requires careful case analysis.; It can be slightly harder to derive and implement correctly compared to the doubled array approach.
### Explanation
This optimal solution avoids any extra space by directly calculating the components needed to construct the answer. The logic is the same as the previous approach but implemented more efficiently.

The maximum subarray can be:
1.  Contained entirely within one copy of `arr`. The max sum is `kadane_max`.
2.  Spanning across a boundary. The best case for a subarray spanning two arrays is `max_suffix_sum + max_prefix_sum`.

Combining these, the maximum sum within two concatenations is `max(kadane_max, max_prefix_sum + max_suffix_sum)`.

- If `total_sum <= 0`, this is our final answer, as more concatenations don't help.
- If `total_sum > 0`, we can potentially form a larger sum by taking a suffix, all `k-2` middle arrays, and a prefix. This gives a candidate sum of `max_suffix_sum + max_prefix_sum + (k-2) * total_sum`. The final answer is the maximum of this and `kadane_max`.

All these components (`kadane_max`, `total_sum`, `max_prefix_sum`, `max_suffix_sum`) can be computed with a few passes over the original array, using only constant extra space.

```java
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        long MOD = 1_000_000_007;
        int n = arr.length;

        long kadaneMax = 0;
        long currentMax = 0;
        for (int x : arr) {
            currentMax += x;
            if (currentMax < 0) {
                currentMax = 0;
            }
            kadaneMax = Math.max(kadaneMax, currentMax);
        }

        if (k == 1) {
            return (int) (kadaneMax % MOD);
        }

        long maxPrefixSum = 0;
        long maxSuffixSum = 0;
        long totalSum = 0;
        long currentPrefixSum = 0;
        for (int x : arr) {
            totalSum += x;
            currentPrefixSum += x;
            maxPrefixSum = Math.max(maxPrefixSum, currentPrefixSum);
        }

        long currentSuffixSum = 0;
        for (int i = n - 1; i >= 0; i--) {
            currentSuffixSum += arr[i];
            maxSuffixSum = Math.max(maxSuffixSum, currentSuffixSum);
        }

        long ans;
        if (totalSum <= 0) {
            ans = Math.max(kadaneMax, maxPrefixSum + maxSuffixSum);
        } else {
            long spanningSum = maxPrefixSum + maxSuffixSum + (long)(k - 2) * totalSum;
            ans = Math.max(kadaneMax, spanningSum);
        }

        return (int) (ans % MOD);
    }
}
```
### Algorithm
- Calculate `kadane_max`, the maximum subarray sum of `arr` (allowing for an empty subarray sum of 0).
- If `k == 1`, the answer is simply `kadane_max`.
- Calculate `total_sum`, the sum of all elements in `arr`.
- Calculate `max_prefix_sum`, the maximum sum of a prefix of `arr` (can be 0).
- Calculate `max_suffix_sum`, the maximum sum of a suffix of `arr` (can be 0).
- **If `total_sum <= 0`**: The maximum sum cannot be improved by including full arrays. The answer is the maximum of `kadane_max` (subarray within one `arr`) and `max_prefix_sum + max_suffix_sum` (subarray spanning two `arr`s).
- **If `total_sum > 0`**: The maximum sum can be improved by including `k-2` full arrays. The candidate sum is `max_prefix_sum + max_suffix_sum + (k-2) * total_sum`. The answer is the maximum of this candidate and `kadane_max`.
- Return the final answer modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution {
public
  int kConcatenationMaxSum(int[] arr, int k) {
    long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
    for (int x : arr) {
      s += x;
      mxPre = Math.max(mxPre, s);
      miPre = Math.min(miPre, s);
      mxSub = Math.max(mxSub, s - miPre);
    }
    long ans = mxSub;
    final int mod = (int)1 e9 + 7;
    if (k == 1) {
      return (int)(ans % mod);
    }
    long mxSuf = s - miPre;
    ans = Math.max(ans, mxPre + mxSuf);
    if (s > 0) {
      ans = Math.max(ans, (k - 2) * s + mxPre + mxSuf);
    }
    return (int)(ans % mod);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int kConcatenationMaxSum(vector<int> &arr, int k) {
    long s = 0, mxPre = 0, miPre = 0, mxSub = 0;
    for (int x : arr) {
      s += x;
      mxPre = max(mxPre, s);
      miPre = min(miPre, s);
      mxSub = max(mxSub, s - miPre);
    }
    long ans = mxSub;
    const int mod = 1e9 + 7;
    if (k == 1) {
      return ans % mod;
    }
    long mxSuf = s - miPre;
    ans = max(ans, mxPre + mxSuf);
    if (s > 0) {
      ans = max(ans, mxPre + (k - 2) * s + mxSuf);
    }
    return ans % mod;
  }
};

```

### Python

```python
class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int: s = mx_pre = mi_pre = mx_sub = 0 for x in arr: s += x mx_pre = max(mx_pre, s) mi_pre = min(mi_pre, s) mx_sub = max(mx_sub, s - mi_pre) ans = mx_sub mod = 10 ** 9 + 7 if k == 1: return ans % mod mx_suf = s - mi_pre ans = max(ans, mx_pre + mx_suf) if s > 0: ans = max(ans, (k - 2) * s + mx_pre + mx_suf) return ans % mod

```