Watch 10 video solutions for K-Concatenation Maximum Sum, a medium level problem involving Array, Dynamic Programming. This walkthrough by Pepcoding has 18,678 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= k <= 105-104 <= arr[i] <= 104Problem 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 | 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 |