K-Concatenation Maximum Sum: Extending Kadane's to Repeated Arrays

You are given an integer array arr and an integer k. The k-concatenation of arr is the array formed by concatenating arr with itself k times. Find the maximum subarray sum in the k-concatenation. If the result is negative or zero, return 0. Return the answer modulo 10^9 + 7.

This is LeetCode 1191: K-Concatenation Maximum Sum, and it is a natural extension of the classic Maximum Subarray problem. You cannot actually build the concatenated array when k could be up to 100,000, so you need a smarter approach. The trick is to realize there are only three cases to consider, and each one builds on Kadane's algorithm.

Why this problem matters

K-Concatenation Maximum Sum forces you to think beyond the standard Kadane's template. It tests whether you truly understand why Kadane's works, because you need to extend the logic to handle repetition without materializing the repeated array. The three-case decomposition (single copy, two copies, and many copies with positive total) is a pattern that shows up whenever you need to reason about periodic or repeating structures.

The key insight

The maximum subarray in a k-concatenated array can only look like one of three things:

1. Contained in a single copy. The best subarray fits entirely within one copy of arr. Standard Kadane's on a single copy finds this.

2. Spanning two adjacent copies. The best subarray starts somewhere in one copy and ends somewhere in the next. This is the max suffix of one copy plus the max prefix of the next copy. Running Kadane's on two concatenated copies also captures this.

3. Spanning many copies (when k >= 3 and the total sum is positive). If the total sum of arr is positive, then every additional full copy in the middle adds to the answer. The best subarray becomes: max suffix + (k-2) full copies + max prefix.

If the total sum is zero or negative, extra middle copies never help. Cases 1 and 2 are all you need. If the total sum is positive and k >= 3, case 3 dominates.

The solution

def kConcatenationMaxSum(arr, k):
    MOD = 10**9 + 7
    n = len(arr)
    total = sum(arr)

    kadane_one = kadane(arr)

    if k == 1:
        return kadane_one % MOD

    prefix_max = 0
    running = 0
    for val in arr:
        running += val
        prefix_max = max(prefix_max, running)

    suffix_max = 0
    running = 0
    for i in range(n - 1, -1, -1):
        running += arr[i]
        suffix_max = max(suffix_max, running)

    two_copy = suffix_max + prefix_max

    if total > 0:
        multi_copy = suffix_max + (k - 2) * total + prefix_max
    else:
        multi_copy = two_copy

    return max(kadane_one, two_copy, multi_copy) % MOD


def kadane(arr):
    max_sum = 0
    cur = 0
    for val in arr:
        cur = max(cur + val, val)
        cur = max(cur, 0)
        max_sum = max(max_sum, cur)
    return max_sum

The function starts by computing Kadane's result on a single copy. If k == 1, that is the answer.

For k >= 2, we compute the maximum prefix sum (best sum starting from the beginning of arr) and the maximum suffix sum (best sum ending at the end of arr). The two-copy case is simply the suffix of one copy glued to the prefix of the next.

For k >= 3, if the total sum of arr is positive, we can sandwich k - 2 full copies between the suffix and prefix. Each full copy adds total to the sum. If the total is not positive, those extra copies would only hurt, so we skip them.

The final answer is the maximum of all cases, taken modulo 10^9 + 7.

Visual walkthrough

Let's trace through arr = [1, -2, 1] with k = 5. The total sum is 0, so extra middle copies do not help.

The answer is 2, coming from the suffix of one copy (the trailing 1) plus the prefix of the next copy (the leading 1). Even though we have 5 copies, the negative total sum means we cannot do better than this cross-boundary subarray.

Complexity analysis

Time: O(n). We make three passes over the array: one for Kadane's, one for prefix sums, and one for suffix sums. Each pass is O(n). The value of k does not affect runtime because we use multiplication instead of iteration for the middle copies.

Space: O(1). A handful of variables regardless of input size. We never build the concatenated array.

The building blocks

1. Kadane's algorithm (extend or restart)

The foundation of this problem is the same extend-or-restart decision from Maximum Subarray. At each element, either continue the current subarray or start fresh. This gives you the best subarray within a single copy in O(n).

cur = max(cur + val, val)
max_sum = max(max_sum, cur)

The only twist here is that we clamp cur and max_sum to 0, because the problem requires returning 0 for non-positive results.

2. Prefix and suffix max sums

To handle the cross-boundary case, you need the best "tail" of one copy and the best "head" of the next. The max prefix sum is the largest sum of arr[0..i] for any i. The max suffix sum is the largest sum of arr[j..n-1] for any j. Both are computed in a single pass each.

prefix_max = 0
running = 0
for val in arr:
    running += val
    prefix_max = max(prefix_max, running)

This is a pattern you will see in Maximum Sum Circular Subarray as well. Whenever a subarray can wrap or span boundaries, prefix and suffix decomposition is the tool to reach for.

Edge cases

• k = 1: Only case 1 applies. Run Kadane's on the single copy and return the result.
• All elements negative like arr = [-1, -2], k = 3: Kadane's returns 0 (since the problem says non-positive results become 0), and prefix/suffix maxes are also 0. Answer is 0.
• All elements positive like arr = [1, 2], k = 3: The entire concatenation is the best subarray. suffix + (k-2)*total + prefix = 3 + 3 + 3 = 9.
• Total sum is exactly 0 like arr = [1, -1], k = 100000: Extra copies do not help. The answer comes from either a single-copy Kadane or the two-copy cross-boundary case.
• Single element like arr = [5], k = 1: Answer is 5. arr = [-3], k = 1: Answer is 0.
• Large k but negative total: Even with k = 100000, if total is negative or zero, cases 1 and 2 cover everything. No need to iterate.

From understanding to recall

You now understand the three-case decomposition: single-copy Kadane, cross-boundary suffix+prefix, and the multi-copy extension when the total is positive. The logic is clean. But in an interview, will you remember to handle the k = 1 base case separately? Will you remember that extra copies only help when the total sum is strictly positive?

Spaced repetition bridges this gap. You revisit the k-concatenation pattern at increasing intervals, writing the prefix/suffix logic and the three-case formula from scratch each time. After a few reps, the decomposition becomes automatic.

The prefix/suffix decomposition and the extend-or-restart DP are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding problems randomly and hoping the patterns stick.

Related posts

• Maximum Subarray - The foundation: Kadane's algorithm for maximum contiguous subarray sum
• Maximum Sum Circular Subarray - Another Kadane extension that handles wrap-around using min subarray complement
• Maximum Product Subarray - Kadane variant tracking both max and min running values for products