Skip to main content
Talentd

K-Concatenation Maximum Sum - Solution & Explanation

MediumArrayDynamic Programming12 min readAsked at: Google
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJava

Python

Java

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.

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.

Code

C++JavaScript

C++

JavaScript

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

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

Video Solution

K Concatenation Maximum Sum Dynamic Programming | Leetcode-1191 (Medium) Solution • Pepcoding • 18,947 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice K-Concatenation Maximum Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays