problemmediumalgorithmsleetcode-3381leetcode 3381leetcode3381

Maximum Subarray Sum With Length Divisible by K

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

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.

Examples

Example 1

Input: nums = [1,2], k = 1
Output: 3
Explanation:
The subarray `[1, 2]` with sum 3 has length equal to 2 which is divisible by
1.

Example 2

Input: nums = [-1,-2,-3,-4,-5], k = 4
Output: -10
Explanation:
The maximum sum subarray is `[-1, -2, -3, -4]` which has length equal to 4
which is divisible by 4.

Example 3

Input: nums = [-5,1,2,-3,4], k = 2
Output: 4
Explanation:
The maximum sum subarray is `[1, 2, -3, 4]` which has length equal to 4 which
is divisible by 2.

Constraints

  • 1 <= k <= nums.length <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9

Solution

Method 1 – Prefix Sum with Hash Map

Intuition

We want the maximum subarray sum whose length is divisible by k. For each prefix sum, we can use a hash map to store the minimum prefix sum for each modulo class of the index. This allows us to efficiently check all subarrays of length divisible by k.

Approach

  1. Compute prefix sums of the array.
  2. For each index i, let mod = i % k. Store the minimum prefix sum seen so far for each mod in a hash map.
  3. For each index, the maximum subarray sum ending at i with length divisible by k is prefix[i] - min_prefix[mod].
  4. Update the answer with the maximum found.

Code

C++
class Solution {
public:
    int maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> prefix(n+1);
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + nums[i];
        vector<long long> min_prefix(k, LLONG_MAX);
        min_prefix[0] = 0;
        long long ans = LLONG_MIN;
        for (int i = 1; i <= n; ++i) {
            int mod = i % k;
            if (min_prefix[mod] != LLONG_MAX)
                ans = max(ans, prefix[i] - min_prefix[mod]);
            min_prefix[mod] = min(min_prefix[mod], prefix[i]);
        }
        return ans;
    }
};
Go
import "math"
func maximumSubarraySum(nums []int, k int) int {
    n := len(nums)
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + nums[i]
    }
    minPrefix := make([]int, k)
    for i := range minPrefix {
        minPrefix[i] = math.MaxInt64
    }
    minPrefix[0] = 0
    ans := math.MinInt64
    for i := 1; i <= n; i++ {
        mod := i % k
        if minPrefix[mod] != math.MaxInt64 {
            if prefix[i]-minPrefix[mod] > ans {
                ans = prefix[i] - minPrefix[mod]
            }
        }
        if prefix[i] < minPrefix[mod] {
            minPrefix[mod] = prefix[i]
        }
    }
    return ans
}
Java
class Solution {
    public int maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n+1];
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + nums[i];
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE);
        minPrefix[0] = 0;
        long ans = Long.MIN_VALUE;
        for (int i = 1; i <= n; ++i) {
            int mod = i % k;
            if (minPrefix[mod] != Long.MAX_VALUE)
                ans = Math.max(ans, prefix[i] - minPrefix[mod]);
            minPrefix[mod] = Math.min(minPrefix[mod], prefix[i]);
        }
        return (int)ans;
    }
}
Kotlin
class Solution {
    fun maximumSubarraySum(nums: IntArray, k: Int): Int {
        val n = nums.size
        val prefix = LongArray(n+1)
        for (i in 0 until n) prefix[i+1] = prefix[i] + nums[i]
        val minPrefix = LongArray(k) { Long.MAX_VALUE }
        minPrefix[0] = 0L
        var ans = Long.MIN_VALUE
        for (i in 1..n) {
            val mod = i % k
            if (minPrefix[mod] != Long.MAX_VALUE)
                ans = maxOf(ans, prefix[i] - minPrefix[mod])
            minPrefix[mod] = minOf(minPrefix[mod], prefix[i])
        }
        return ans.toInt()
    }
}
Python
class Solution:
    def maximumSubarraySum(self, nums: list[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n+1)
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
        min_prefix = [float('inf')] * k
        min_prefix[0] = 0
        ans = float('-inf')
        for i in range(1, n+1):
            mod = i % k
            if min_prefix[mod] != float('inf'):
                ans = max(ans, prefix[i] - min_prefix[mod])
            min_prefix[mod] = min(min_prefix[mod], prefix[i])
        return ans
Rust
impl Solution {
    pub fn maximum_subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
        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; }
        let mut min_prefix = vec![i64::MAX; k as usize];
        min_prefix[0] = 0;
        let mut ans = i64::MIN;
        for i in 1..=n {
            let m = i % k as usize;
            if min_prefix[m] != i64::MAX {
                ans = ans.max(prefix[i] - min_prefix[m]);
            }
            min_prefix[m] = min_prefix[m].min(prefix[i]);
        }
        ans as i32
    }
}
TypeScript
class Solution {
    maximumSubarraySum(nums: number[], k: number): number {
        const n = nums.length;
        const prefix: number[] = Array(n+1).fill(0);
        for (let i = 0; i < n; ++i) prefix[i+1] = prefix[i] + nums[i];
        const minPrefix: number[] = Array(k).fill(Infinity);
        minPrefix[0] = 0;
        let ans = -Infinity;
        for (let i = 1; i <= n; ++i) {
            const mod = i % k;
            if (minPrefix[mod] !== Infinity)
                ans = Math.max(ans, prefix[i] - minPrefix[mod]);
            minPrefix[mod] = Math.min(minPrefix[mod], prefix[i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We scan the array once.
  • 🧺 Space complexity: O(k), for the min_prefix array.

Comments