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.
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.
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.
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.
C++
JavaScript
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.
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:
k = 1, the answer is mxSub.k \ge 2, if the maximum subarray spans two arr, then the answer is mxPre + mxSuf, where mxSuf = s - miPre.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.
| 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 | — |
| 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 |
K Concatenation Maximum Sum Dynamic Programming | Leetcode-1191 (Medium) Solution • Pepcoding • 18,678 views views
Watch 9 more video solutions →Practice K-Concatenation Maximum Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor