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.

Example 1

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4
5

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
  • -109 <= nums[i] <= 10^9

Examples

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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.