K-Concatenation Maximum Sum
MedPrompt
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: 9Example 2:
Input: arr = [1,-2,1], k = 5
Output: 2Example 3:
Input: arr = [-1,-2], k = 7
Output: 0
Constraints:
1 <= arr.length <= 1051 <= k <= 105-104 <= arr[i] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- The core idea is to simulate running Kadane's algorithm on the full concatenated array of size
n * kwithout actually constructing it. - The
i-th element of this virtual array can be accessed asarr[i % n]. - We maintain two
longvariables:max_so_farto store the maximum sum found anywhere (initialized to 0, for the empty subarray case), andmax_ending_hereto store the maximum sum of a subarray ending at the current position. - We loop from
i = 0ton * k - 1. - In each iteration, we get the current element
arr[(int)(i % n)]and add it tomax_ending_here. - We update
max_so_far = max(max_so_far, max_ending_here). - If
max_ending_herebecomes negative, we reset it to 0, as a negative-sum prefix won't contribute to a larger maximum sum. - Finally, we return
max_so_farmodulo10^9 + 7.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
Pros
Simple to understand and implement.
Directly applies a well-known algorithm to the problem's structure.
Cons
Extremely inefficient for large values of
kandn.Will result in a Time Limit Exceeded (TLE) error on most platforms for the given constraints.
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.
Algorithm
- Handle the base case
k=1. The answer is the result of Kadane's algorithm on the originalarr, with a floor of 0. - For
k > 1, create a new arraytwo_arrof size2*nby concatenatingarrwith itself. - Calculate
max_sum_for_two, the maximum subarray sum oftwo_arrusing Kadane's algorithm. - Calculate
total_sumof the originalarr. - If
total_sum <= 0: The answer ismax(0, max_sum_for_two). Concatenating more arrays won't help. - If
total_sum > 0: The answer ismax_sum_for_two + (k-2) * total_sum. We take the best sum from two arrays and add the positive contribution of the remainingk-2arrays. - The final result must be taken modulo
10^9 + 7, ensuring it's non-negative.
Walkthrough
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 ofarrin the middle, which would not increase (and likely decrease) the sum. Therefore, the maximum sum is confined to what can be found inarrconcatenated with itself (arr+arr). -
Case 2:
total_sum > 0. If the sum is positive, each full copy ofarrcontributes 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 remainingk-2full copies ofarr. 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.
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; }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- Calculate
kadane_max, the maximum subarray sum ofarr(allowing for an empty subarray sum of 0). - If
k == 1, the answer is simplykadane_max. - Calculate
total_sum, the sum of all elements inarr. - Calculate
max_prefix_sum, the maximum sum of a prefix ofarr(can be 0). - Calculate
max_suffix_sum, the maximum sum of a suffix ofarr(can be 0). - If
total_sum <= 0: The maximum sum cannot be improved by including full arrays. The answer is the maximum ofkadane_max(subarray within onearr) andmax_prefix_sum + max_suffix_sum(subarray spanning twoarrs). - If
total_sum > 0: The maximum sum can be improved by includingk-2full arrays. The candidate sum ismax_prefix_sum + max_suffix_sum + (k-2) * total_sum. The answer is the maximum of this candidate andkadane_max. - Return the final answer modulo
10^9 + 7.
Walkthrough
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:
- Contained entirely within one copy of
arr. The max sum iskadane_max. - 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, allk-2middle arrays, and a prefix. This gives a candidate sum ofmax_suffix_sum + max_prefix_sum + (k-2) * total_sum. The final answer is the maximum of this andkadane_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.
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); }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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); }}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; }};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 % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.