Maximum subarray sum with length divisible by k

Array Hash Table Prefix Sum

49.6% acceptance

Feb 24, 2026

681

You are given an array of integers nums and an integer k. Return the maximum sum of a subarray of nums, such that the size of the subarray is divisible by k.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
    // prefix[i] = sum of nums[0..i]
    // subarray [l..r] (length (r-l) divisible by k) => (r-l) % k == 0 => r % k == l % k
    // For each remainder r mod k, track min prefix sum seen so far
    // For each i (end of subarray at i must have length at least k, so i >= k)
    // We want max (prefix[i] - prefix[j]) where j <= i-k and (i-j) % k == 0
    
    let k = k as usize;
    let n = nums.len();
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }
    
    // For each remainder mod k, track min prefix sum at indices with same remainder
    // but only those at index <= i-k
    let mut min_prefix = vec![i64::MAX; k];
    let mut ans = i64::MIN;
    
    for i in k..=n {
      // prefix[i-k] has remainder (i-k) % k = i % k (since k % k = 0)
      let rem = (i - k) % k;
      let prev = prefix[i - k];
      if prev < min_prefix[rem] {
        min_prefix[rem] = prev;
      }
      let cur_rem = i % k;
      if min_prefix[cur_rem] != i64::MAX {
        let val = prefix[i] - min_prefix[cur_rem];
        if val > ans {
          ans = val;
        }
      }
    }
    ans
  }
}