Maximum Subarray Sum With Length Divisible by K

Problem Description

Ah, the classic “Maximum Subarray Sum With Length Divisible by K” problem! It’s like trying to find the perfect slice of pizza at a party where everyone is fighting over the last piece. You want the biggest slice (maximum sum) but it has to be a specific size (length divisible by K). Imagine you’re at a buffet, and you can only take a plate that can hold exactly 4 pieces of sushi. You want to maximize your sushi intake, but you can only take plates that fit that exact number.

In simpler terms, given an array of integers, you need to find the maximum sum of a contiguous subarray whose length is divisible by a given integer K. Sounds easy, right? Well, it’s a bit trickier than it seems, especially when you have to keep track of those pesky prefix sums!

Code Solution


import math

class Solution:
    def maxSubarraySum(self, nums: list[int], k: int) -> int:
        ans = -math.inf
        prefix = 0
        minPrefix = [math.inf] * k
        minPrefix[k - 1] = 0

        for i, num in enumerate(nums):
            prefix += num
            ans = max(ans, prefix - minPrefix[i % k])
            minPrefix[i % k] = min(minPrefix[i % k], prefix)

        return ans

Approach Explanation

The approach here is to maintain a running prefix sum while also keeping track of the minimum prefix sums for each modulo class (i.e., i % k). As we iterate through the array, we calculate the maximum subarray sum by subtracting the minimum prefix sum from the current prefix sum. This way, we ensure that the length of the subarray is divisible by K. It’s like keeping a diary of your sushi intake while ensuring you only write down the best days!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(k)

Real-World Example

Let’s say you’re a student trying to maximize your study hours for exams. You can only study in blocks of 3 hours (K=3). You want to find the maximum study hours you can accumulate in a week, but you can only count those blocks that fit perfectly into your schedule. This problem is akin to finding the maximum sum of study hours that fit into your 3-hour blocks!