Problem Statement in English

Approach

The idea is to use prefix sums and a hashmap to store the minimum prefix sum for each possible remainder when the length of the subarray is divided by k.

Then for any given current sum, we can simply check the hashmap for the prefix sum that would give us a subarray length divisible by k and calculate the maximum subarray sum accordingly.

Solution in Python


class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        hm = {}
        hm[0] = 0
        curr = 0
        res = -inf

        for r, num in enumerate(nums):
            curr += num

            key = (r + 1) % k
            res = max(res, curr - hm.get(key, inf))
            hm[key] = min(hm.get(key, inf), curr)

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the array once.

  • Space: $O(k)$
    Since we are storing at most k different remainders in the hashmap.

Mistakes I Made

I forgot to subtract the prefix sum from the current sum to get the maximum subarray sum.

And we are done.