Maximum Subarray Sum With Length Divisible by K

main.md

Question

Approach

I convert the array into prefix sums and observe that a subarray nums[l..r-1] has length divisible by k iff the prefix indices l and r have the same remainder modulo k (because r-l ≡ 0 (mod k)). So for each prefix index i I keep the smallest prefix sum seen so far among indices with remainder i % k. The best subarray ending at i with allowed length is prefix[i] - min_prefix[i % k]. I scan i from 0..n, update the answer using that formula, and then update the stored minimum for i % k.

Implementation

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = 0
        INF = 10**30
        min_pref = [INF] * k
        min_pref[0] = 0
        
        ans = -INF
        for i in range(1, n + 1):
            prefix += nums[i - 1]
            r = i % k
            if min_pref[r] != INF:
                ans = max(ans, prefix - min_pref[r])
            min_pref[r] = min(min_pref[r], prefix)
        
        return ans

Complexities

• Time: O(n)
• Space: O(k)