Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1191. K-Concatenation Maximum Sum - Leetcode Solution

Code Implementation

class Solution:
    def kConcatenationMaxSum(self, arr, k):
        MOD = 10**9 + 7

        def kadane(a):
            max_ending_here = max_so_far = 0
            for x in a:
                max_ending_here = max(x, max_ending_here + x)
                max_so_far = max(max_so_far, max_ending_here)
            return max_so_far

        arr_sum = sum(arr)
        max_kadane = kadane(arr)
        if k == 1:
            return max_kadane % MOD

        # For k >= 2, consider arr concatenated twice
        max_kadane_twice = kadane(arr * 2)
        if arr_sum > 0:
            return (max_kadane_twice + (k - 2) * arr_sum) % MOD
        else:
            return max_kadane_twice % MOD
      
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        const int MOD = 1e9 + 7;
        long long arr_sum = 0;
        for (int x : arr) arr_sum += x;
        long long max_kadane = 0, max_ending_here = 0;
        for (int x : arr) {
            max_ending_here = max((long long)x, max_ending_here + x);
            max_kadane = max(max_kadane, max_ending_here);
        }
        if (k == 1) return max_kadane % MOD;

        // Kadane on arr concatenated twice
        int n = arr.size();
        max_ending_here = max_kadane = 0;
        for (int i = 0; i < n * 2; ++i) {
            int x = arr[i % n];
            max_ending_here = max((long long)x, max_ending_here + x);
            max_kadane = max(max_kadane, max_ending_here);
        }
        if (arr_sum > 0) {
            return (max_kadane + ((k - 2) * arr_sum) % MOD) % MOD;
        } else {
            return max_kadane % MOD;
        }
    }
};
      
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        final int MOD = 1000000007;
        long arrSum = 0;
        for (int x : arr) arrSum += x;

        long maxKadane = 0, maxEndingHere = 0;
        for (int x : arr) {
            maxEndingHere = Math.max(x, maxEndingHere + x);
            maxKadane = Math.max(maxKadane, maxEndingHere);
        }
        if (k == 1) return (int)(maxKadane % MOD);

        // Kadane on arr concatenated twice
        int n = arr.length;
        maxEndingHere = maxKadane = 0;
        for (int i = 0; i < n * 2; ++i) {
            int x = arr[i % n];
            maxEndingHere = Math.max(x, maxEndingHere + x);
            maxKadane = Math.max(maxKadane, maxEndingHere);
        }
        if (arrSum > 0) {
            return (int)((maxKadane + ((k - 2) * arrSum) % MOD) % MOD);
        } else {
            return (int)(maxKadane % MOD);
        }
    }
}
      
var kConcatenationMaxSum = function(arr, k) {
    const MOD = 1e9 + 7;
    function kadane(a) {
        let maxEndingHere = 0, maxSoFar = 0;
        for (const x of a) {
            maxEndingHere = Math.max(x, maxEndingHere + x);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
    const arrSum = arr.reduce((a, b) => a + b, 0);
    const maxKadane = kadane(arr);
    if (k === 1) return maxKadane % MOD;

    // Kadane on arr concatenated twice
    const maxKadaneTwice = kadane(arr.concat(arr));
    if (arrSum > 0) {
        return (maxKadaneTwice + (k - 2) * arrSum) % MOD;
    } else {
        return maxKadaneTwice % MOD;
    }
};

Problem Description

Given an integer array arr and an integer k, you are asked to form a new array by concatenating arr to itself k times (i.e., the new array is arr repeated k times in a row). Your task is to find the maximum possible sum of a non-empty subarray in this new array.

  • You may choose any non-empty subarray (a contiguous segment) from the concatenated array.
  • The answer can be large, so return it modulo 10^9 + 7.
  • Constraints:
    • 1 <= arr.length <= 10^5
    • 1 <= k <= 10^5
    • -10^4 <= arr[i] <= 10^4

Thought Process

At first glance, the problem seems to ask for the maximum subarray sum of a very large array (potentially up to 10^{10} elements if both arr and k are large). A brute-force approach would be to generate the full concatenated array and then apply Kadane’s algorithm to find the maximum subarray sum. However, this is not feasible due to memory and time constraints.

We need to find a way to compute the answer without actually building the huge array. Notice that the structure of the array repeats, and the only places where "wrapping" can increase the sum is at the boundary between the repeated arr blocks. Thus, the solution must consider subarrays that:

  • Are entirely within one copy of arr
  • Start at the end of one copy and continue into the next (i.e., cross the boundary), especially for k > 1
  • Potentially span multiple full copies of arr if arr has a positive sum
The goal is to use Kadane’s algorithm and some clever observations about prefix and suffix sums to handle all cases efficiently.

Solution Approach

  • Step 1: Kadane's Algorithm on arr
    • Apply Kadane's algorithm to arr to find the maximum subarray sum within a single copy. This covers subarrays that do not cross any boundaries.
  • Step 2: Handle k == 1
    • If k is 1, the answer is simply the result from Step 1.
  • Step 3: Kadane's Algorithm on arr concatenated twice
    • Concatenate arr to itself once (i.e., arr + arr) and run Kadane's algorithm again. This captures any maximum subarray that crosses the boundary between two consecutive copies of arr.
  • Step 4: Consider the Total Sum
    • If the total sum of arr is positive, then using more copies of arr will increase the total sum. The optimal subarray could include the entire middle section of arr\) repeated (\(k-2\)) times, sandwiched between the best suffix of the first copy and the best prefix of the last copy.
    • So, the formula becomes: max_subarray_sum = max(max_kadane_twice, max_kadane_twice + (k-2) * arr_sum)
  • Step 5: Modulo Operation
    • Since the answer can be very large, take the result modulo 10^9 + 7 before returning.

This approach ensures we never construct the full concatenated array and runs efficiently in linear time relative to the original arr length.

Example Walkthrough

Example:
arr = [1, -2, 1], k = 5

  1. Compute arr_sum = 1 + (-2) + 1 = 0
  2. Run Kadane's algorithm on arr:
    • Start: max_so_far = 0, max_ending_here = 0
    • 1: max_ending_here = max(1, 0+1) = 1, max_so_far = 1
    • -2: max_ending_here = max(-2, 1-2) = -1, max_so_far = 1
    • 1: max_ending_here = max(1, -1+1) = 1, max_so_far = 1
    So, max_kadane = 1
  3. Run Kadane's algorithm on arr + arr = [1, -2, 1, 1, -2, 1]:
    • Process as above, max_so_far = 2
  4. Since arr_sum = 0 (not positive), the answer is 2.
  5. Return 2 modulo 10^9+7 (which is just 2).

Time and Space Complexity

  • Brute-force Approach:
    • Time: O(nk) (where n is the length of arr and k can be up to 10^5)
    • Space: O(nk) (would require storing the entire concatenated array)
    • This is infeasible for large k and n.
  • Optimized Approach (the one above):
    • Time: O(n) (Kadane’s algorithm runs twice over arr of length n)
    • Space: O(1) (no extra storage proportional to k or n)
    • This is efficient and scales well for all allowed input sizes.

Summary

The K-Concatenation Maximum Sum problem challenges us to find the maximum subarray sum in a virtually huge array formed by repeating arr k times. By leveraging Kadane’s algorithm and understanding how positive sums allow us to "chain together" multiple copies of arr, we avoid brute-force and gain both speed and clarity. The key insight is that the only interesting subarrays either fit within one or two copies, or stretch across the full length when arr is positive. This elegant reduction allows for an efficient, scalable solution.