K-Concatenation Maximum Sum

medium kadane prefix sum dynamic programming

Problem

Given an integer array arr and an integer k, form a new array by repeating arr exactly k times. Return the maximum sub-array sum of that array (the empty sub-array, with sum 0, is allowed). Because the answer can be large, return it modulo 10⁹ + 7.

Inputarr = [1, -2, 1], k = 5

Output2

The total sum (0) is not positive, so the best window lives inside just two copies: [1, -2, 1, 1] picks the trailing 1 of one copy and leading 1 of the next, giving 2.

arr (comma-separated)

def k_concatenation_max_sum(arr, k):
    MOD = 10**9 + 7
    total = sum(arr)
    # Kadane over min(k, 2) copies.
    best = cur = 0
    doubled = arr * min(k, 2)
    for x in doubled:
        cur = max(0, cur + x)
        best = max(best, cur)
    # If k >= 3 and the whole array is positive, glue (k-2) full copies.
    if k >= 3 and total > 0:
        best = max(best, best + total * (k - 2))
    return best % MOD

function kConcatenationMaxSum(arr, k) {
  const MOD = 1000000007n;
  const total = arr.reduce((a, b) => a + b, 0);
  let best = 0, cur = 0;
  const copies = Math.min(k, 2);
  for (let c = 0; c < copies; c++) {
    for (const x of arr) {
      cur = Math.max(0, cur + x);
      best = Math.max(best, cur);
    }
  }
  let ans = BigInt(best);
  if (k >= 3 && total > 0) {
    ans = ans + BigInt(total) * BigInt(k - 2);
  }
  return Number(((ans % MOD) + MOD) % MOD);
}

class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        long MOD = 1000000007L;
        long total = 0;
        for (int x : arr) total += x;
        long best = 0, cur = 0;
        int copies = Math.min(k, 2);
        for (int c = 0; c < copies; c++) {
            for (int x : arr) {
                cur = Math.max(0, cur + x);
                best = Math.max(best, cur);
            }
        }
        if (k >= 3 && total > 0) {
            best += total * (k - 2);
        }
        return (int) (best % MOD);
    }
}

int kConcatenationMaxSum(vector<int>& arr, int k) {
    const long long MOD = 1000000007LL;
    long long total = 0;
    for (int x : arr) total += x;
    long long best = 0, cur = 0;
    int copies = min(k, 2);
    for (int c = 0; c < copies; c++) {
        for (int x : arr) {
            cur = max(0LL, cur + x);
            best = max(best, cur);
        }
    }
    if (k >= 3 && total > 0) {
        best += total * (long long)(k - 2);
    }
    return (int)(best % MOD);
}

Explanation

We need the largest sub-array sum of arr repeated k times — but k can be huge, so building the whole array is impossible. The insight is that the best window never needs more than two copies plus, maybe, a stack of full copies in the middle.

First we run Kadane's algorithm over min(k, 2) copies. Kadane sweeps once, keeping cur as the best sum ending here (reset to 0 if it goes negative) and best as the overall max. Two copies are enough to capture a window that spills from the end of one copy into the start of the next.

Then, if k >= 3 and the array's total sum is positive, each extra full copy in the middle adds total for free. So we add total * (k - 2) to bridge those middle copies. If the total isn't positive, extra copies only hurt, so we leave best alone.

Example: arr = [1, -2, 1], k = 5. The total is 0 (not positive), so no middle copies help. The best window lives inside two copies — the trailing 1 of one and the leading 1 of the next — giving 2.

Finally we return the result modulo 10^9 + 7.

Time: O(n) Space: O(n)