problemmediumalgorithmsleetcode-1191leetcode 1191leetcode1191

K-Concatenation Maximum Sum

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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 10^9 + 7.

Examples

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 <= 1^05
  • 1 <= k <= 10^5
  • -10^4 <= arr[i] <= 10^4

Solution

Method 1 – Kadane's Algorithm with Prefix/Suffix Sum

Intuition

The maximum subarray sum in the k-concatenated array can be found by considering:

  • The max subarray sum in one array.
  • The max prefix sum + max suffix sum + (k-2)*total sum (if k > 1 and total sum > 0).

Approach

  1. Compute the max subarray sum in arr (Kadane's algorithm).
  2. Compute the max prefix sum and max suffix sum.
  3. If k == 1, answer is max subarray sum.
  4. If k > 1, answer is max(max subarray sum in arr+arr, max prefix + max suffix + (k-2)*total sum).
  5. Return answer modulo 10^9+7.

Code

C++
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int mod = 1e9+7;
        long sum = 0, max_sum = 0, cur = 0;
        for (int x : arr) {
            sum += x;
            cur = max((long)x, cur + x);
            max_sum = max(max_sum, cur);
        }
        long prefix = 0, s = 0;
        for (int x : arr) {
            s += x;
            prefix = max(prefix, s);
        }
        long suffix = 0; s = 0;
        for (int i = arr.size()-1; i >= 0; --i) {
            s += arr[i];
            suffix = max(suffix, s);
        }
        if (k == 1) return max_sum % mod;
        long ans = max(max_sum, prefix + suffix + max(0L, sum)*(k-2));
        return ans % mod;
    }
};
Go
func kConcatenationMaxSum(arr []int, k int) int {
    mod := int(1e9+7)
    sum, maxSum, cur := 0, 0, 0
    for _, x := range arr {
        sum += x
        cur = max(x, cur+x)
        maxSum = max(maxSum, cur)
    }
    prefix, s := 0, 0
    for _, x := range arr {
        s += x
        prefix = max(prefix, s)
    }
    suffix, s := 0, 0
    for i := len(arr)-1; i >= 0; i-- {
        s += arr[i]
        suffix = max(suffix, s)
    }
    if k == 1 {
        return maxSum % mod
    }
    ans := max(maxSum, prefix+suffix+max(0, sum)*(k-2))
    return ans % mod
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
Java
class Solution {
    public int kConcatenationMaxSum(int[] arr, int k) {
        int mod = 1000000007;
        long sum = 0, maxSum = 0, cur = 0;
        for (int x : arr) {
            sum += x;
            cur = Math.max(x, cur + x);
            maxSum = Math.max(maxSum, cur);
        }
        long prefix = 0, s = 0;
        for (int x : arr) {
            s += x;
            prefix = Math.max(prefix, s);
        }
        long suffix = 0; s = 0;
        for (int i = arr.length-1; i >= 0; --i) {
            s += arr[i];
            suffix = Math.max(suffix, s);
        }
        if (k == 1) return (int)(maxSum % mod);
        long ans = Math.max(maxSum, prefix + suffix + Math.max(0, sum)*(k-2));
        return (int)(ans % mod);
    }
}
Kotlin
class Solution {
    fun kConcatenationMaxSum(arr: IntArray, k: Int): Int {
        val mod = 1000000007
        var sum = 0L; var maxSum = 0L; var cur = 0L
        for (x in arr) {
            sum += x
            cur = maxOf(x.toLong(), cur + x)
            maxSum = maxOf(maxSum, cur)
        }
        var prefix = 0L; var s = 0L
        for (x in arr) {
            s += x
            prefix = maxOf(prefix, s)
        }
        var suffix = 0L; s = 0L
        for (i in arr.indices.reversed()) {
            s += arr[i]
            suffix = maxOf(suffix, s)
        }
        if (k == 1) return (maxSum % mod).toInt()
        val ans = maxOf(maxSum, prefix + suffix + maxOf(0L, sum)*(k-2))
        return (ans % mod).toInt()
    }
}
Python
class Solution:
    def kConcatenationMaxSum(self, arr: list[int], k: int) -> int:
        mod = 10**9+7
        def kadane(a):
            cur = ans = 0
            for x in a:
                cur = max(x, cur+x)
                ans = max(ans, cur)
            return ans
        total = sum(arr)
        prefix = suffix = s = 0
        for x in arr:
            s += x
            prefix = max(prefix, s)
        s = 0
        for x in arr[::-1]:
            s += x
            suffix = max(suffix, s)
        if k == 1:
            return kadane(arr) % mod
        ans = max(kadane(arr*2), prefix + suffix + max(0, total)*(k-2))
        return ans % mod
Rust
impl Solution {
    pub fn k_concatenation_max_sum(arr: Vec<i32>, k: i32) -> i32 {
        let modv = 1_000_000_007;
        let sum: i64 = arr.iter().map(|&x| x as i64).sum();
        let mut max_sum = 0i64;
        let mut cur = 0i64;
        for &x in &arr {
            cur = (x as i64).max(cur + x as i64);
            max_sum = max_sum.max(cur);
        }
        let mut prefix = 0i64; let mut s = 0i64;
        for &x in &arr {
            s += x as i64;
            prefix = prefix.max(s);
        }
        let mut suffix = 0i64; s = 0i64;
        for &x in arr.iter().rev() {
            s += x as i64;
            suffix = suffix.max(s);
        }
        if k == 1 {
            return max_sum as i32 % modv;
        }
        let ans = max_sum.max(prefix + suffix + sum.max(0) * (k as i64 - 2));
        (ans % modv) as i32
    }
}
TypeScript
class Solution {
    kConcatenationMaxSum(arr: number[], k: number): number {
        const mod = 1e9+7
        const kadane = (a: number[]) => {
            let cur = 0, ans = 0
            for (const x of a) {
                cur = Math.max(x, cur+x)
                ans = Math.max(ans, cur)
            }
            return ans
        }
        const total = arr.reduce((a, b) => a+b, 0)
        let prefix = 0, s = 0
        for (const x of arr) {
            s += x
            prefix = Math.max(prefix, s)
        }
        s = 0
        for (let i = arr.length-1; i >= 0; --i) {
            s += arr[i]
            suffix = Math.max(suffix, s)
        }
        if (k === 1) return kadane(arr) % mod
        const ans = Math.max(kadane(arr.concat(arr)), prefix + suffix + Math.max(0, total)*(k-2))
        return ans % mod
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Kadane's algorithm and prefix/suffix sums.
  • 🧺 Space complexity: O(1) — Only a few variables are used.

Comments