K-Concatenation Maximum Sum — Medium Problem & Solution

Problem statement

Build a new array by writing arr out k times back to back. For example, arr = [1, 2] with k = 3 gives [1, 2, 1, 2, 1, 2].

Return the maximum sum of a contiguous subarray of this new array. The subarray may be empty, in which case its sum is 0.

The answer can be very large, so return it modulo 10^9 + 7.

Example 1

Input: arr = [3,-1], k = 3
Output: 7
Explanation: `[3,-1,3,-1,3,-1]`: take `3,-1,3,-1,3`.

Example 2

Input: arr = [2,-5,1], k = 4
Output: 3
Explanation: The copies lose value overall; the best is `1, 2` across one boundary.

Example 3

Input: arr = [10000,10000], k = 100000
Output: 999999993
Explanation: The whole array sums to `2 * 10^9`, which is `999999993` modulo `10^9 + 7`.

Constraints

• 1 <= arr.length <= 10^5
• 1 <= k <= 10^5
• -10^4 <= arr[i] <= 10^4

How to solve K-Concatenation Maximum Sum

A best subarray spanning several copies is a suffix + some whole copies + a prefix; whole copies are worth including exactly when arr sums to something positive.

Approach

1. If k == 1, return Kadane's maximum (with the empty subarray allowed) on arr.
2. Otherwise compute best2, Kadane's maximum over two concatenated copies — this covers every subarray within one copy and every suffix + prefix pair.
3. Let total be the sum of arr. If total > 0, add (k - 2) * total.
4. Return the result modulo 10^9 + 7.

Why it works

A subarray of the k-fold array either fits inside two adjacent copies or contains at least one full copy. If it contains m >= 1 full copies plus a suffix and a prefix, then with total > 0 it is best to take all k - 2 middle copies, while with total <= 0 dropping full copies never hurts, so it reduces to the two-copy case. When total > 0 the best two-copy subarray is in fact a suffix + prefix pair, so adding (k - 2) * total to it is valid.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The empty subarray is allowed, so an all-negative array answers 0.
• (k - 2) * total reaches about 10^14 — compute in 64 bits and take the modulus only at the end (the maximum must be compared before reducing).
• For k == 1 do not run on two copies — that would allow a subarray that wraps around.

Reference solution

Python

from typing import List

def kConcatenationMaxSum(arr: List[int], k: int) -> int:
    MOD = 10 ** 9 + 7

    def kadane(times):
        best = cur = 0
        for _ in range(times):
            for a in arr:
                cur = max(cur + a, a)
                best = max(best, cur)
        return best

    if k == 1:
        return kadane(1) % MOD
    best = kadane(2)
    total = sum(arr)
    if total > 0:
        best += (k - 2) * total
    return best % MOD

JavaScript

var kConcatenationMaxSum = function(arr, k) {
    var MOD = 1000000007;
    var kadane = function(times) {
        var best = 0, cur = 0;
        for (var t = 0; t < times; t++) {
            for (var i = 0; i < arr.length; i++) {
                cur = Math.max(cur + arr[i], arr[i]);
                if (cur > best) best = cur;
            }
        }
        return best;
    };
    if (k === 1) return kadane(1) % MOD;
    var total = 0;
    for (var j = 0; j < arr.length; j++) total += arr[j];
    var best = kadane(2);
    if (total > 0) best += (k - 2) * total;
    return best % MOD;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium