K concatenation maximum sum

Array Dynamic Programming

25.2% acceptance

Feb 25, 2026

1503

134

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 109 + 7.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn k_concatenation_max_sum(arr: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let _n = arr.len();
    // Max subarray of single array (Kadane)
    let kadane = |v: &[i32]| -> i64 {
      let mut max_sum = 0i64;
      let mut cur = 0i64;
      for &x in v {
        cur = (cur + x as i64).max(0);
        max_sum = max_sum.max(cur);
      }
      max_sum
    };
    let total: i64 = arr.iter().map(|&x| x as i64).sum();
    if k == 1 {
      return (kadane(&arr) % MOD) as i32;
    }
    // max subarray crossing the boundary: suffix_max + prefix_max
    let mut suffix_max = 0i64;
    let mut running = 0i64;
    for &x in arr.iter().rev() {
      running += x as i64;
      suffix_max = suffix_max.max(running);
    }
    let mut prefix_max = 0i64;
    running = 0;
    for &x in &arr {
      running += x as i64;
      prefix_max = prefix_max.max(running);
    }
    let cross = suffix_max + prefix_max;
    // If total > 0, we can gain extra by repeating (k-2) times middle arrays
    let result = if total > 0 {
      kadane(&arr).max(cross + total * (k as i64 - 2))
    } else {
      kadane(&arr).max(cross)
    };
    (result.max(0) % MOD) as i32
  }
}