1191. K-Concatenation Maximum Sum - Solution

The 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 10⁹ + 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⁵
1 <= k <= 10⁵
-10⁴ <= arr[i] <= 10⁴

Approach overview

Problem Overview: Given an integer array arr and an integer k, the array is concatenated k times. The task is to compute the maximum possible subarray sum from this large virtual array. The result must be returned modulo 1e9 + 7. The challenge is handling very large k without actually building the concatenated array.

Approach 1: Kadane's Algorithm Extension (O(n) time, O(1) space)

This approach extends the classic maximum subarray technique from dynamic programming. First run Kadane’s algorithm on the original array to compute the best subarray sum inside one copy. Next consider the effect of concatenation. If the total sum of the array is positive, repeating the array increases the maximum subarray because middle copies contribute their full sum. In that case compute Kadane on two concatenated arrays to capture cross-boundary subarrays, then add (k-2) * totalSum. If the total sum is non‑positive, the best result always appears within at most two copies of the array. This method avoids constructing the full repeated array and only scans the input a few times.

Approach 2: Prefix-Suffix Combination (O(n) time, O(n) space)

This method explicitly analyzes boundary contributions using prefix and suffix sums. Compute the maximum prefix sum (best sum starting from index 0) and the maximum suffix sum (best sum ending at the last index). Any subarray that crosses the boundary between concatenated copies must combine a suffix from one copy and a prefix from the next. If the total array sum is positive and k > 2, additional middle copies contribute full array sums. The final candidate becomes maxSuffix + maxPrefix + (k-2) * totalSum. Also compare this value with the best subarray found inside a single array using Kadane’s algorithm. This approach highlights the structure of cross-boundary subarrays and works well when reasoning about repeated array segments.

Both approaches avoid building the actual k-concatenated array, which would be infeasible for large k. Instead they analyze the properties of subarrays across boundaries. The key observation: any optimal subarray spans at most two copies unless the total array sum is positive, in which case additional full arrays contribute linearly.

Recommended for interviews: The Kadane’s Algorithm extension is what most interviewers expect. It demonstrates understanding of maximum subarray patterns and how to adapt them when arrays repeat. The prefix-suffix method also scores well because it clearly explains cross-boundary contributions and shows strong reasoning about array sums.

Approach 1: Kadane's Algorithm Extension

This approach extends the classical Kadane's algorithm by considering different configurations of k. Specifically, it takes into account whether we can multiply the array multiple times or focus on subarrays crossing the splits between original and its copies.

If k is 1, return the maximum subarray using Kadane's algorithm. For larger k values, consider using up to two copies of the array and add the total array sum to gain potential full repetitions benefits due to positive arrays.

Python

def k_concatenation_max_sum(arr, k):
    MOD = 10**9 + 7
    def max_subarray_sum(a):
        max_ending_here = max_so_far = 0
        for x in a:
            max_ending_here = max(x, max_ending_here + x)
            max_so_far = max(max_so_far, max_ending_here)
        return max_so_far
    
    arr_sum = sum(arr)
    max_kadane = max_subarray_sum(arr)
    max_double = max_subarray_sum(arr * 2)
    
    if k == 1:
        return max_kadane % MOD
    else:
        return max(max_double, max_kadane + (k - 2) * max(0, arr_sum)) % MOD

Java

public class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        int MOD = 1000000007;
        long maxKadane = kadane(arr);
        if (k == 1) return (int)(maxKadane % MOD);
        
        long maxDoubleKadane = kadane(concatenate(arr));
        long arrSum = 0;
        for (int num : arr) {
            arrSum += num;
        }
        
        long result = Math.max(maxDoubleKadane, maxKadane + Math.max(0, arrSum) * (k - 2));
        return (int)(result % MOD);
    }
    
    private long kadane(int[] arr) {
        long maxEndingHere = 0, maxSoFar = 0;
        for (int num : arr) {
            maxEndingHere = Math.max(num, maxEndingHere + num);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
    
    private int[] concatenate(int[] arr) {
        int[] result = new int[arr.length * 2];
        System.arraycopy(arr, 0, result, 0, arr.length);
        System.arraycopy(arr, 0, result, arr.length, arr.length);
        return result;
    }
}

The function calculates the maximum subarray sum using Kadane's algorithm, both for one array and two copies of the array. It then decides whether using the sum of the entire array multiple times benefits the result based on whether the total sum is positive. Finally, it calculates and returns the maximum subarray sum for k repetitions.

Complexity

Time Complexity: O(n) since Kadane's algorithm is O(n), similarly calculating the doubled array sum is still O(n) when considering bearable constants. Space Complexity: O(1) since the space usage is independent of array size.

Try this approach in the editor

Approach 2: Prefix-Suffix Combination

This approach utilizes prefix and suffix sums to consider all possible beneficial array joins. By calculating possible sums from connecting prefixes and suffixes, it checks maximum subarray sums within possible single, double, or full length connections.

C++

#include <vector>
#include <algorithm>

int kConcatenationMaxSum(std::vector<int>& arr, int k) {
    const int MOD = 1000000007;
    int n = arr.size();
    long long arrSum = 0, currMax = 0, totalMax = 0;
    
    long long prefixSum = 0, suffixSum = 0, currPrefix = 0, currSuffix = 0;
    for (int i = 0; i < n; ++i) {
        arrSum += arr[i];
    }
    
    for (int i = 0; i < n; ++i) {
        currMax = std::max((long long)arr[i], currMax + arr[i]);
        totalMax = std::max(totalMax, currMax);
        currPrefix += arr[i];
        prefixSum = std::max(prefixSum, currPrefix);
    }
    currMax = 0;
    for (int i = n - 1; i >= 0; --i) {
        currSuffix += arr[i];
        suffixSum = std::max(suffixSum, currSuffix);
    }
    
    if (k == 1) return totalMax % MOD;
    
    long long maxSubArraySum = std::max(suffixSum + prefixSum, totalMax);
    if (arrSum > 0) maxSubArraySum = std::max(maxSubArraySum, prefixSum + suffixSum + (k - 2) * arrSum);
    
    return maxSubArraySum % MOD;
}

JavaScript

function kConcatenationMaxSum(arr, k) {
    const MOD = 1000000007;
    const n = arr.length;
    let totalSum = arr.reduce((acc, val) => acc + val, 0);
    let prefixSum = 0, suffixSum = 0, maxPrefix = 0, maxSuffix = 0;
    let currentMax = 0, totalMax = 0;

    for (let i = 0; i < n; i++) {
        currentMax = Math.max(arr[i], currentMax + arr[i]);
        totalMax = Math.max(totalMax, currentMax);
        prefixSum += arr[i];
        maxPrefix = Math.max(maxPrefix, prefixSum);
    }
    currentMax = 0;
    for (let i = n - 1; i >= 0; i--) {
        suffixSum += arr[i];
        maxSuffix = Math.max(maxSuffix, suffixSum);
    }

    if (k === 1) return totalMax % MOD;

    let result = Math.max(maxPrefix + maxSuffix, totalMax);
    if (totalSum > 0) {
        result = Math.max(result, maxPrefix + maxSuffix + (k - 2) * totalSum);
    }

    return result % MOD;
}

The algorithm first computes classic prefix and suffix sums. It combines these sums with checking the maximum within a single instance or two full copies. Finally, if k > 2 and the entire array's sum is positive, it considers the added benefit of inserting multiple total array sums into the result.

Complexity

Time Complexity: O(n) because of traversals to compute prefix and suffix sums, which are limited to a singular concatenation of the array. Space Complexity: O(1) as no additional data structures proportional to input size are used.

Try this approach in the editor

Approach 3: Prefix Sum + Case Discussion

We denote the sum of all elements in the array arr as s, the maximum prefix sum as mxPre, the minimum prefix sum as miPre, and the maximum subarray sum as mxSub.

We traverse the array arr. For each element x, we update s = s + x, mxPre = max(mxPre, s), miPre = min(miPre, s), mxSub = max(mxSub, s - miPre).

Next, we consider the value of k:

When k = 1, the answer is mxSub.
When k \ge 2, if the maximum subarray spans two arr, then the answer is mxPre + mxSuf, where mxSuf = s - miPre.
When k \ge 2 and s > 0, if the maximum subarray spans three arr, then the answer is (k - 2) times s + mxPre + mxSuf.

Finally, we return the result of the answer modulo 10^9 + 7.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array arr.

func kConcatenationMaxSum(arr []int, k int) int {
	var s, mxPre, miPre, mxSub int
	for _, x := range arr {
		s += x
		mxPre = max(mxPre, s)
		miPre = min(miPre, s)
		mxSub = max(mxSub, s-miPre)
	}
	const mod = 1e9 + 7
	ans := mxSub
	if k == 1 {
		return ans % mod
	}
	mxSuf := s - miPre
	ans = max(ans, mxSuf+mxPre)
	if s > 0 {
		ans = max(ans, mxSuf+(k-2)*s+mxPre)
	}
	return ans % mod
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Kadane's Algorithm Extension	Time Complexity: O(n) since Kadane's algorithm is O(n), similarly calculating the doubled array sum is still O(n) when considering bearable constants. Space Complexity: O(1) since the space usage is independent of array size.
Prefix-Suffix Combination	Time Complexity: O(n) because of traversals to compute prefix and suffix sums, which are limited to a singular concatenation of the array. Space Complexity: O(1) as no additional data structures proportional to input size are used.
Prefix Sum + Case Discussion	–

Complexity analysis

Approach	Time	Space	When to Use
Kadane's Algorithm Extension	O(n)	O(1)	General case and most interview scenarios; fastest and simplest adaptation of maximum subarray
Prefix-Suffix Combination	O(n)	O(n)	When analyzing cross-boundary subarrays explicitly or explaining repeated array behavior

Frequently asked questions

Is K-Concatenation Maximum Sum easy or hard?

K-Concatenation Maximum Sum is rated Medium difficulty on LeetCode. The tricky part is realizing that the optimal subarray can span multiple concatenated copies and that Kadane’s algorithm must be adapted instead of constructing the full repeated array.

K-Concatenation Maximum Sum Python/Java solution

Typical implementations apply Kadane’s algorithm with integer accumulation and modular arithmetic for the final result. Python and Java versions iterate through the array once or twice while tracking the current and global maximum sums.

How to solve K-Concatenation Maximum Sum in O(n)?

Compute the maximum subarray using Kadane’s algorithm. Calculate the total sum of the array. If the total sum is positive and k > 1, evaluate the best subarray across two concatenations and add (k-2) times the total sum. Otherwise the answer is simply the best subarray found within one or two copies.

What is the best approach for K-Concatenation Maximum Sum?

Kadane’s Algorithm extension is the most common solution. Run Kadane on one or two copies of the array and use the total array sum to determine whether additional concatenations increase the result. The algorithm runs in O(n) time and O(1) space.

Is K-Concatenation Maximum Sum asked at Google/Amazon/Meta?

This problem follows a classic maximum subarray pattern and variations of it appear in interviews at companies like Amazon, Google, and Meta. Interviewers often expect candidates to recognize Kadane’s algorithm and extend it for repeated arrays.

What data structure is used in K-Concatenation Maximum Sum?

The problem primarily uses arrays and dynamic programming ideas. Kadane’s algorithm maintains running sums while scanning the array, and the prefix-suffix approach uses prefix and suffix sums derived from the same array.

What is the time complexity of K-Concatenation Maximum Sum?

The optimal solutions run in O(n) time where n is the length of the input array. Only a few passes over the array are required to compute the total sum, maximum subarray sum, and prefix or suffix values.

K-Concatenation Maximum Sum solution and explanation

The problem

Approach overview

Approach 1: Kadane's Algorithm Extension

Approach 2: Prefix-Suffix Combination

Approach 3: Prefix Sum + Case Discussion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

K-Concatenation Maximum Sum solution and explanation

The problem

Approach overview

Approach 1: Kadane's Algorithm Extension

Approach 2: Prefix-Suffix Combination

Approach 3: Prefix Sum + Case Discussion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems