Problem Description

You are given an integer array arr and an integer k. Your task is to create a modified array by repeating the original array k times consecutively, then find the maximum sum of any contiguous subarray within this modified array.

For instance, if arr = [1, 2] and k = 3, the modified array becomes [1, 2, 1, 2, 1, 2].

The key points to understand:

• The subarray can have length 0 (empty subarray), which has a sum of 0
• You need to find the maximum possible sum among all contiguous subarrays
• Since the answer can be very large, return the result modulo 10^9 + 7

The challenge lies in efficiently computing the maximum subarray sum without actually creating the concatenated array, which could be extremely large. The solution requires analyzing different cases based on:

• How the optimal subarray might span across the array repetitions
• Whether including multiple complete copies of the array increases the sum
• The relationship between prefix sums, suffix sums, and the total array sum

The algorithm uses Kadane's algorithm principles combined with prefix/suffix sum analysis to handle three scenarios:

1. The optimal subarray is contained within a single copy of arr
2. The optimal subarray spans across two copies (ending in one and starting in the next)
3. The optimal subarray includes multiple complete copies of arr (when the total sum is positive)

Intuition

When we concatenate an array k times, we need to think about where the maximum subarray could possibly be located. Let's break this down step by step.

First, consider the simplest case where k = 1. This is just the classic maximum subarray problem that can be solved using Kadane's algorithm. We track the minimum prefix sum seen so far (miPre) and for each position, the maximum subarray ending at that position is the current prefix sum minus the minimum prefix sum before it.

Now, when k ≥ 2, things get interesting. The maximum subarray could be:

1. Entirely within one copy of the array - This is the same as the k = 1 case, giving us mxSub.

2. Spanning across two adjacent copies - It could end somewhere in the first copy and start somewhere in the second copy. This means we take the maximum suffix of one array (which is s - miPre where s is the total sum) and combine it with the maximum prefix of the next array (mxPre). This gives us mxSuf + mxPre.

3. Including multiple complete copies - If the total sum s of the array is positive, then including more complete copies in between will only increase our sum. The optimal configuration would be: maximum suffix of the first copy + several complete middle copies + maximum prefix of the last copy. With k total copies, we have (k-2) complete middle copies, giving us mxSuf + (k-2) * s + mxPre.

The key insight is that we don't need to check all possible subarrays in the concatenated array. Due to the repetitive nature, if a subarray spans more than two copies, the only way it can be optimal is if we're including complete copies in the middle (which only helps if s > 0).

By computing just a few values during a single pass through the original array - the total sum, maximum prefix, minimum prefix (to get maximum suffix), and maximum subarray sum - we can determine the answer for any value of k without actually creating the concatenated array.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation uses a single-pass algorithm with prefix sum tracking to solve this problem efficiently. Let's walk through the key components:

Variables Initialization:

• s: Running sum of all elements (prefix sum)
• mx_pre: Maximum prefix sum seen so far
• mi_pre: Minimum prefix sum seen so far
• mx_sub: Maximum subarray sum within a single array

First Pass - Computing Key Values:

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)

For each element x:

1. Update the running sum s
2. Track the maximum prefix sum encountered
3. Track the minimum prefix sum encountered
4. Calculate the maximum subarray sum using the formula s - mi_pre, which represents the maximum sum of any subarray ending at the current position

Computing Maximum Suffix: After the loop, we calculate mx_suf = s - mi_pre. This represents the maximum suffix sum of the array (the best sum starting from some position and going to the end).

Case Analysis Based on k:

1. When k = 1:

   • Simply return mx_sub % mod since we only have one copy of the array

2. When k ≥ 2:

   • First, consider subarrays spanning two copies: ans = max(ans, mx_pre + mx_suf)
   • This combines the best suffix from one copy with the best prefix from the next copy

3. When k ≥ 2 and s > 0:

   • Consider including complete middle copies: ans = max(ans, (k - 2) * s + mx_pre + mx_suf)
   • This adds (k-2) complete copies between the optimal suffix and prefix
   • We only do this when s > 0 because adding complete copies with negative sum would decrease our total

Final Step: Return ans % mod where mod = 10^9 + 7 to handle large numbers as required.

The algorithm achieves O(n) time complexity with O(1) space complexity, making it highly efficient even for large arrays and large values of k.

Example Walkthrough

Let's walk through the solution with arr = [1, -2, 1] and k = 5.

Step 1: Single Pass Through Array

We'll track our variables as we iterate:

• At index 0: s = 1, this is our best prefix so far (mx_pre = 1), and best subarray is [1] with sum 1
• At index 1: s = -1, we found a new minimum prefix (mi_pre = -1), best subarray remains [1]
• At index 2: s = 0, the best subarray ending here is s - mi_pre = 0 - (-1) = 1, but we also check if we can do better by taking elements from earlier: the subarray [1, -2, 1] has sum 0, but [2, 1] has sum 0 - (-1) = 1, and [-2, 1] has sum -1 - 0 = -1. Actually, the best subarray is now [1] at index 0 or [1] at index 2, both with sum 1. Wait, let me recalculate: mx_sub = max(1, 0 - (-1)) = max(1, 1) = 1. Actually, the subarray from after index 1 to index 2 is just [1] with sum 1. But the subarray from index 0 to index 2 minus the prefix before index 0 is [1, -2, 1] with sum 0. The subarray from index 0 to index 2 minus the prefix up to index 0 (which is 0) gives sum 0. The subarray starting after the minimum prefix point (after index 1) to the current position (index 2) gives us the maximum. Since mi_pre = -1 occurred at index 1, the subarray from index 2 to index 2 is [1] with sum 1. But we need to check all subarrays ending at position 2. The key insight: s - mi_pre = 0 - (-1) = 1 gives us the maximum subarray ending at position 2, which could be [1] alone or any subarray that avoids the negative prefix.

Let me recalculate more carefully:

• After processing [1]: prefix_sum = 1, max_subarray_so_far = 1 (the subarray [1])
• After processing [1, -2]: prefix_sum = -1, max_subarray_so_far = 1 (still [1])
• After processing [1, -2, 1]: prefix_sum = 0. To find max subarray ending here, we look at current_prefix - min_prefix_before = 0 - (-1) = 1. This represents taking elements after the minimum point up to current position. The maximum subarray is either a previous one (sum = 1) or one ending here (sum = 1), so mx_sub = max(1, 1) = 1.

Actually, let's be more precise. At index 2, s - mi_pre = 0 - (-1) = 1. This represents the subarray that starts right after where we had the minimum prefix sum (which was at index 1 with value -1) and goes to the current position. So we're looking at the subarray [1] at index 2, which has sum 1. But we also need to check if including more elements helps. The subarray [1, -2, 1] has sum 0, and [-2, 1] has sum -1, so the best subarray ending at index 2 is indeed [1] with sum 1.

However, I realize there's an issue with my tracking. Let me recalculate: when we compute s - mi_pre, if mi_pre was achieved at position j, then we're computing the sum of subarray from position j+1 to current position i. At index 2, with s = 0 and mi_pre = -1 (achieved at index 1), we get 0 - (-1) = 1. But this doesn't give us the subarray [1] at index 2.

Let me think again. The prefix sum at index 1 is -1 (sum of [1, -2]). The prefix sum at index 2 is 0 (sum of [1, -2, 1]). The subarray from index 2 to index 2 (just [1]) has sum = prefix[2] - prefix[1] = 0 - (-1) = 1. That's correct!

So mx_sub = 1 (best subarray within single copy).

Step 2: Calculate Maximum Suffix mx_suf = s - mi_pre = 0 - (-1) = 1

This represents the maximum suffix sum, which is the subarray [1] at the end.

Step 3: Determine Answer Based on k = 5

Since k ≥ 2, we check:

• Option 1: Best within single copy = mx_sub = 1
• Option 2: Spanning two copies = mx_pre + mx_suf = 1 + 1 = 2
  • This would be taking [1] from end of one copy and [1] from start of next copy

Since s = 0 (not positive), we don't consider adding complete middle copies.

Final Answer: 2

The maximum subarray sum is 2, achieved by taking the last element from one copy and the first element from the next copy in the sequence [1, -2, 1, 1, -2, 1, ...].

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. The algorithm makes a single pass through the array, performing constant-time operations (addition, max/min comparisons) for each element. The loop iterates exactly n times, and all operations outside the loop (including the final comparisons and modulo operation) take constant time.

The space complexity is O(1). The algorithm uses only a fixed number of variables (s, mx_pre, mi_pre, mx_sub, ans, mod, mx_suf) regardless of the input size. No additional data structures that scale with input size are created, making the space usage constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Empty Subarray Case

One of the most common mistakes is not properly initializing variables to 0, which implicitly handles the empty subarray case. If all elements in the array are negative, the maximum sum should be 0 (empty subarray), not the least negative number.

Incorrect approach:

max_subarray_sum = float('-inf')  # Wrong initialization
max_prefix_sum = float('-inf')    # Wrong initialization

Correct approach:

max_subarray_sum = 0  # Allows for empty subarray
max_prefix_sum = 0    # Start with 0 for proper comparison

2. Incorrect Modulo Application

Applying modulo operation too early or incorrectly can lead to wrong results when comparing values.

Incorrect approach:

# Applying modulo during intermediate calculations
result = (max_prefix_sum % MOD + max_suffix_sum % MOD) % MOD
if total_sum > 0:
    result = max(result, ((k - 2) * total_sum % MOD + max_prefix_sum % MOD + max_suffix_sum % MOD) % MOD)

Correct approach:

# Keep calculations without modulo until the final return
result = max(result, max_prefix_sum + max_suffix_sum)
if total_sum > 0:
    result = max(result, (k - 2) * total_sum + max_prefix_sum + max_suffix_sum)
return result % MOD  # Apply modulo only at the end

3. Misunderstanding the Suffix Calculation

A common error is calculating the maximum suffix incorrectly by iterating backwards or using complex logic.

Incorrect approach:

# Unnecessarily complex backward iteration
max_suffix_sum = 0
suffix_sum = 0
for i in range(len(arr) - 1, -1, -1):
    suffix_sum += arr[i]
    max_suffix_sum = max(max_suffix_sum, suffix_sum)

Correct approach:

# Elegant calculation using the relationship: max_suffix = total_sum - min_prefix
max_suffix_sum = total_sum - min_prefix_sum

4. Not Checking if Total Sum is Positive Before Including Middle Arrays

Including complete middle arrays when the total sum is negative or zero will decrease the overall sum.

Incorrect approach:

if k >= 2:
    # Always considering middle arrays regardless of total sum
    result = max(result, (k - 2) * total_sum + max_prefix_sum + max_suffix_sum)

Correct approach:

if k >= 2 and total_sum > 0:  # Only include middle arrays if beneficial
    result = max(result, (k - 2) * total_sum + max_prefix_sum + max_suffix_sum)

5. Integer Overflow in Languages with Fixed Integer Size

While Python handles large integers automatically, in languages like Java or C++, the multiplication (k - 2) * total_sum can overflow.

Solution for other languages:

// Use long type in Java
long result = Math.max(result, (long)(k - 2) * totalSum + maxPrefix + maxSuffix);

6. Off-by-One Error with k Values

Misunderstanding when to apply which formula based on k value.

Incorrect approach:

if k > 2:  # Wrong condition - misses k=2 case
    result = max(result, max_prefix_sum + max_suffix_sum)

Correct approach:

if k >= 2:  # Include k=2 case for suffix+prefix combination
    result = max(result, max_prefix_sum + max_suffix_sum)