{x}
blog image

K-Concatenation Maximum Sum

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

Solution Explanation: 1191. K-Concatenation Maximum Sum

This problem asks to find the maximum subarray sum after concatenating an array arr k times. A naive approach would be to concatenate the array k times and then use Kadane's algorithm to find the maximum subarray sum. However, this approach has a time complexity of O(n*k), where n is the length of the array. For large values of k and n, this would be inefficient. The optimal solution leverages prefix sums and careful case analysis to achieve a linear time complexity.

Approach: Prefix Sum and Case Analysis

The solution uses a clever approach combining prefix sum calculations with case analysis based on the value of k and the sum of the elements in arr.

  1. Prefix Sum Calculation: The code first calculates the following using a single pass through the array:

    • s: The total sum of all elements in arr.
    • mxPre: The maximum prefix sum encountered while traversing arr.
    • miPre: The minimum prefix sum encountered while traversing arr.
    • mxSub: The maximum subarray sum within a single arr. This is calculated using the formula max(mxSub, s - miPre). This efficiently handles the case where the maximum sum subarray starts before and ends after a point of minimum cumulative sum within a single array.

  2. Case Analysis Based on k:

    • k == 1: If k is 1, the maximum subarray sum is simply mxSub, which has already been calculated.

    • k >= 2: When k is greater than or equal to 2, the maximum subarray sum can span across multiple concatenated arrays. We consider several possibilities:

      • Maximum subarray within two consecutive arrays: The maximum subarray sum might be formed by concatenating the maximum suffix of one arr (calculated as s-miPre, denoted as mxSuf) with the maximum prefix of the next arr (mxPre). This is max(mxSub, mxPre + mxSuf).

      • Maximum subarray spanning across more than two arrays (only if s > 0): If the total sum of arr (s) is positive, concatenating multiple copies of arr will always increase the total sum. In this case, the maximum subarray sum can span across more than two arrays. The formula (k-2)*s + mxPre + mxSuf accounts for this situation. We add (k-2)*s because we have k arrays and we've already covered the max sum across two.

  3. Modulo Operation: Finally, the result is taken modulo 10^9 + 7 to handle potential integer overflow.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array arr. This is because the algorithm performs a single pass through the array to calculate the prefix sums and then performs constant-time case analysis.

  • Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store variables like s, mxPre, miPre, mxSub, and mxSuf.

Code Examples (Python, Java, C++, Go)

The code examples provided in the problem description are efficient implementations of this approach. They directly translate the algorithmic steps outlined above. They handle edge cases and efficiently compute the required values using a linear scan of the input array. The modulo operation ensures that results are within the specified bounds.