Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3653. Maximum Subarray Sum With Length Divisible by K

My accepted Python solution to LeetCode problem 3653, Maximum Subarray Sum With Length Divisible by K, running in 423ms.

  • Difficulty: Medium
  • Python
  • Runtime 423ms
  • Memory 62.9MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 423ms, memory 62.9MB, accepted 2025-12-31.

python
class Solution:
    def maxSubarraySum(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]
        
        # For each position i, we want to find j < i such that (i - j) % k == 0
        # This means i % k == j % k
        # We want to maximize prefix[i] - prefix[j], so minimize prefix[j]
        
        min_prefix = {0: 0}  # min_prefix[r] = minimum prefix sum for index with mod k = r
        max_sum = float('-inf')
        
        for i in range(1, n + 1):
            r = i % k
            if r in min_prefix:
                max_sum = max(max_sum, prefix[i] - min_prefix[r])
            if r not in min_prefix:
                min_prefix[r] = prefix[i]
            else:
                min_prefix[r] = min(min_prefix[r], prefix[i])
        
        return max_sum

Source