You are given an array of integers nums and an integer k. Return the maximum sum of a subarray of nums, such that the size of the subarray is divisible by k.

maxSubarraySum.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSubarraySum = function(nums, k) {
    let n = nums.length;

    // Step 1: Build prefix sums
    let prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    // Step 2: Track the minimum prefix sum for each remainder class
    // Initialize with Infinity (we'll minimize later)
    let minPrefix = new Array(k).fill(Infinity);

    // Step 3: Result variable
    let maxSum = -Infinity;

    // Step 4: Iterate through prefix sums
    for (let i = 0; i <= n; i++) {
        let remainder = i % k;

        // If we've seen this remainder before, we can form a valid subarray
        if (minPrefix[remainder] !== Infinity) {
            maxSum = Math.max(maxSum, prefix[i] - minPrefix[remainder]);
        }

        // Update the minimum prefix sum for this remainder
        minPrefix[remainder] = Math.min(minPrefix[remainder], prefix[i]);
    }

    return maxSum;
};