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] <= 104The key idea behind solving K-Concatenation Maximum Sum is to adapt Kadane’s Algorithm, which efficiently finds the maximum subarray sum in linear time. Since the array can be repeated k times, a naive approach of constructing the full concatenated array would be inefficient when k is large.
Start by computing the maximum subarray sum for a single array using Kadane’s algorithm. If k = 1, this result is sufficient. For larger values of k, observe how the total array sum affects the answer. If the total sum of the array is positive, repeating the array increases the possible maximum subarray sum. In this case, combining prefix sums and suffix sums across concatenated arrays helps capture the best cross-boundary subarray.
This approach avoids explicitly building the repeated array and instead relies on dynamic programming insights and prefix/suffix calculations. The algorithm runs in O(n) time while maintaining constant extra space, making it efficient even for large values of k.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Kadane’s Algorithm on Single Array | O(n) | O(1) |
| Prefix + Suffix with K Concatenation Insight | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How to solve the problem for k=1 ?
Use Kadane's algorithm for k=1.
What are the possible cases for the answer ?
The answer is the maximum between, the answer for k=1, the sum of the whole array multiplied by k, or the maximum suffix sum plus the maximum prefix sum plus (k-2) multiplied by the whole array sum for k > 1.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews, especially for companies focusing on algorithmic problem solving. It tests knowledge of Kadane’s Algorithm, array manipulation, and optimization for large input constraints.
No complex data structure is required. The problem primarily relies on array traversal, prefix and suffix sum calculations, and dynamic programming concepts to determine the maximum possible subarray sum.
The optimal approach extends Kadane’s Algorithm to handle repeated arrays. By analyzing the total sum, prefix maximum, and suffix maximum, you can determine the best possible subarray across concatenations without constructing the entire repeated array.
Kadane’s Algorithm efficiently computes the maximum subarray sum in linear time. It serves as the foundation for solving this problem because the repeated arrays can be analyzed through maximum prefix and suffix combinations.