Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a fixed starting offset modulo k, split the remaining array into consecutive complete blocks of length k. Any allowed subarray with that offset is a nonempty consecutive sequence of these blocks. Its best sum can be found with Kadane's algorithm on block sums.

Approach

Build prefix sums so each length-k block sum is available in constant time. Try offsets from zero through k - 1. For each offset, move forward in steps of k, considering only blocks fully inside the array.

Before adding a block, discard a negative accumulated sum by resetting it to zero; then add the block sum and update the global answer. This chooses between extending the previous block sequence and starting at the current block.

Initialize the answer to negative infinity and update it only after adding a block, so all-negative arrays still return a nonempty subarray's sum. Every valid subarray belongs to exactly one offset, and the scans together examine only a linear number of complete blocks.

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        p = [nums[0]] * n

        for i in range(1, n):
            p[i] = p[i - 1] + nums[i]

        res = float('-inf')

        for i in range(k):
            curr = i
            cs = 0
            while curr + k <= n:
                if cs < 0:
                    cs = 0
                s = p[curr + k - 1] - (p[curr - 1] if curr - 1 >= 0 else 0)
                cs += s
                res = max(res, cs)
                curr += k

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(n) for prefix sums.